timeval_subtract explanation

Question

With the "timeval_subtract" function to find the time elapsed between two struct timeval types, can someone please explain the purpose of and step by step maths used to "Perform the carry for the later subtraction by updating y" and other sections? I understand the purpose of the function and how to implement it within a program, but I would like to understand how it works inside and cannot find any explanations of this anywhere, and I can't seem to wrap my head around it.

int timeval_subtract (struct timeval *result, struct timeval *x,struct timeval  *y)  
{  
  /* Perform the carry for the later subtraction by updating y. */  
  if (x->tv_usec < y->tv_usec) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }  
  if (x->tv_usec - y->tv_usec > 1000000) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000;  
    y->tv_usec += 1000000 * nsec;  
    y->tv_sec -= nsec;  
  }  
  
  /* Compute the time remaining to wait.
     tv_usec is certainly positive. */  
  result->tv_sec = x->tv_sec - y->tv_sec;  
  result->tv_usec = x->tv_usec - y->tv_usec;  
  
  /* Return 1 if result is negative. */  
  return x->tv_sec < y->tv_sec;  
}

It is a function described in relation to the GNU C library for determining an elapsed time https://ftp.gnu.org/old-gnu/Manuals/glibc-2.2.5/html_node/Elapsed-Time.html so I am not looking for improvements but simply an explanation of why the dividing and adding and subtracting and multiplying within it. What do these specific arithmetic operations achieve?/Why are they done/not done? I have done the stepping through but still can'y get my head around it. I will continue to do so until I do (and even after someone explains it to me) but I was hoping to get some insight from someone who understands it already. The platform is UNIX, which I am new to using, but I don't think it changes the operations that are taking place inside the function. It is more a question about the arithmetic being performed than the algorithm being used.

Answer 1

At first glance, it looks like struct timeval contains a time split into two parts:

• tv_usec - microseconds, ideally should always be under 1000000, but greater values seem to be allowed as suggested by the code
• tv_sec - seconds (the number of multiples of 1000000)

and the time in microseconds is tv_usec + tv_sec * 1000000.

Conversely, one would expect this to be true:

• tv_sec = time in microseconds / 1000000
• tv_usec = time in microseconds % 1000000.

The function appears to calculate the time difference between *x and *y (logically, *x - *y) and store it in another struct timeval, *result.

A simple test program gives us some hints:

#include <stdio.h>

struct timeval
{
  long tv_sec;
  long tv_usec;
};

int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{  
  // preserve *y
  struct timeval yy = *y;
  y = &yy;

  /* Perform the carry for the later subtraction by updating y. */  
  if (x->tv_usec < y->tv_usec) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }  
  if (x->tv_usec - y->tv_usec > 1000000) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000;  
    y->tv_usec += 1000000 * nsec;  
    y->tv_sec -= nsec;  
  }  

  /* Compute the time remaining to wait.
     tv_usec is certainly positive. */  
  result->tv_sec = x->tv_sec - y->tv_sec;  
  result->tv_usec = x->tv_usec - y->tv_usec;  

  /* Return 1 if result is negative. */  
  return x->tv_sec < y->tv_sec;  
}

struct timeval testData00 = { 0, 0 };
struct timeval testData01 = { 0, 1 };

int main(void)
{
  struct timeval diff;
  int res;

  res = timeval_subtract(&diff, &testData00, &testData00);
  printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec);

  res = timeval_subtract(&diff, &testData01, &testData01);
  printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec);

  res = timeval_subtract(&diff, &testData01, &testData00);
  printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec);

  res = timeval_subtract(&diff, &testData00, &testData01);
  printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec);

  return 0;
}

Output (ideone):

0 0:0
0 0:0
0 0:1
1 -1:999999

From the last test result it appears that the function returns (-1):999999 instead of -(0:1). Both values represent the same negative time (or time difference) in microseconds:

• -1 * 1000000 + 999999 = -1
• -(0 * 1000000 + 1) = -1

So, how does it really work?

If x->tv_usec >= y->tv_usec then only the second if could probably^* execute:

  if (x->tv_usec - y->tv_usec > 1000000) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000;  
    y->tv_usec += 1000000 * nsec;  
    y->tv_sec -= nsec;  
  }  

This if checks if the difference in the microseconds parts alone is greater than 1 second. If it is, it subtracts the whole seconds of this difference from y->tv_usec (as microseconds) and adds it to y->tv_sec (as seconds). This simply redistributes the time in *y without really changing it. You could rewrite this if equivalently like this to see it more clearly:

  if (x->tv_usec - y->tv_usec > 1000000) {  
    int nsec = (x->tv_usec - y->tv_usec) / 1000000;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }  

One important thing to note here is that when the input *x and *y have their tv_usec in the range from 0 to 999999 inclusive, the body of this if does not execute (hence, probably^* is actually never when x->tv_usec >= y->tv_usec and when tv_usecs are in the range from 0 to 999999).

The net effect of this if is not readily clear now.

However, one interesting thing can be seen here. If we call this function with *x = 0:1000001 and *y = 0:0, the result is going to be wrong: difference = (-1):2000001 (instead of 1:1) and the return value of the function = 1 (instead of 0). This suggests that the function isn't really suited for tv_usec > 1000000 and even for tv_usec > 999999. And because of this behavior I'm going to claim that the function isn't suited for negative tv_usec in the inputs either. I'm just going to ignore those cases in the face of this behavior. It looks wrong enough already.

Let's look at the first if.

  /* Perform the carry for the later subtraction by updating y. */  
  if (x->tv_usec < y->tv_usec) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }  

As the comment and the code suggests, when x->tv_usec < y->tv_usec we need to take care of the "carry" between the "digits" as if we were adding and not subtracting. But it's OK, we'll see it.

Let's go back to school for a moment.

How do you do 37 - 12?

You do it like this:

7 - 2 = 5
3 - 1 = 2

And so 37 - 12 = 25.

Now, how do you do 57 - 38?

You do it like this:

10/*because 7 < 8*/ + 7 - 8 = 9
5 - 3 - 1/*borrow, because of the above*/ = 1

And so 57 - 38 = 19. See?

And the check:

  if (x->tv_usec < y->tv_usec) {  

checks whether or not we need to take care of this borrowing.

So, what's happening here? Let's look again:

  if (x->tv_usec < y->tv_usec) {  
    int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;  
    y->tv_usec -= 1000000 * nsec;  
    y->tv_sec += nsec;  
  }  

If y->tv_usec > x->tv_usec, it calculates the difference between the two in whole seconds and just like the other if it adds these whole seconds to y->tv_sec and subtracts them from y->tv_usec, simply redistributing the time in *y, without changing it.

The extra one (+ 1) that ends up added to y->tv_sec here will be subtracted from x->tv_sec at the end of the function (result->tv_sec = x->tv_sec - y->tv_sec;) and thus this 1 functions as the borrow I just reminded you of in the 57 - 38 = 19 example.

What else is happening here besides the borrow itself and some time redistribution?

Like I said earlier, I'm just going to ignore negative tv_usecs and greater than 999999 as likely handled incorrectly.

With this I take (y->tv_usec - x->tv_usec) / 1000000 to be 0 and I am left only with truly meaningful values of tv_usecs (0 to 999999 inclusive).

So, if the if's condition is true, I basically subtract 1000000 from y->tv_usec and add 1 (the borrow) to y->tv_sec.

This is the same thing we had in 57 - 38 = 19:

10/*because 7 < 8*/ + 7 - 8 = 9
5 - 3 - 1/*borrow, because of the above*/ = 1

Similarly to this 10, 1000000 is going to be added later in here: result->tv_usec = x->tv_usec - y->tv_usec;

And this first if is the meat of the function.

If I had to write a function with similar behavior, I'd require the input times to be non-negative and the microsecond parts to be no greater than 999999 and I'd write just this:

int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{
  result->tv_sec = x->tv_sec - y->tv_sec;

  if ((result->tv_usec = x->tv_usec - y->tv_usec) < 0)
  {
    result->tv_usec += 1000000;
    result->tv_sec--; // borrow
  }

  return result->tv_sec < 0;
}

If for some odd reason I wanted to support tv_usec > 999999 in the inputs, I'd first move the excess from tv_usec to tv_sec and then do the above, something like this:

int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{
  struct timeval xx = *x;
  struct timeval yy = *y;
  x = &xx; y = &yy;

  if (x->tv_usec > 999999)
  {
    x->tv_sec += x->tv_usec / 1000000;
    x->tv_usec %= 1000000;
  }

  if (y->tv_usec > 999999)
  {
    y->tv_sec += y->tv_usec / 1000000;
    y->tv_usec %= 1000000;
  }

  result->tv_sec = x->tv_sec - y->tv_sec;

  if ((result->tv_usec = x->tv_usec - y->tv_usec) < 0)
  {
    result->tv_usec += 1000000;
    result->tv_sec--; // borrow
  }

  return result->tv_sec < 0;
}

Here, the intent is clear and the code is easy to understand.

Answer 2

Here's a timeval_subtract():

• commented with why and how to carry usec <--> sec
• with const input structs (copies y to the subtrahend sh)
• that normalizes output microseconds (0-999999)

Recall that tv_usec are the microseconds elapsed since tv_sec.
So diff{-1,2000001} == diff{1,1} is true, as is tv{0,-1} == tv{-1,999999}.

/*  copied from
    https://www.gnu.org/software/libc/manual/html_node/Calculating-Elapsed-Time.html
    Changed input timevals to const, added // comments.
    Changed condition of 2nd if.
*/
int
timeval_subtract (const struct timeval *x, const struct timeval *y, struct timeval *diff)
{
    //subtraction found the difference, the minuend minus the subtrahend
    timeval sh = *y;    // mutable local copy of y, sh (the subtrahend)
    /* Perform the carry for the later subtraction by updating sh. */
    if (x->tv_usec < sh.tv_usec) {
        // reduce sh.usecs so usec diff will be positive.
        // carry or lend sh.usecs to sh.secs, in packages of 1e6 usecs (whole secs).
        // as we are here, we know we must carry at least 1 sec (1 million usec)
        int nsec = (sh.tv_usec - x->tv_usec) / 1000000 + 1;
        sh.tv_usec -= 1000000 * nsec;
        sh.tv_sec += nsec;
    }
    // if (x->tv_usec - sh.tv_usec > 1000000) {  // could show tv{x,1000000}, not 'normal'
    if (x->tv_usec - sh.tv_usec > 999999) {      // normalize 0-999999
        // normalize diff; increase sh.usecs so usec diff will be < 1000000.
        // carry or lend whole sh.secs to sh.usecs
        int nsec = (x->tv_usec - sh.tv_usec) / 1000000;
        sh.tv_usec += 1000000 * nsec;
        sh.tv_sec -= nsec;
    }
    // should now have the subtrahend sec/usec that will produce normalized difference
    /*  Compute the time remaining to wait.
        tv_usec is certainly positive. */
    diff->tv_sec = x->tv_sec - sh.tv_sec;
    diff->tv_usec = x->tv_usec - sh.tv_usec;

    /* Return 1 if diff is negative. */
    return x->tv_sec < sh.tv_sec;
    // timeval_subtract
}

If you need to support both 32 and 64 bit time_t types, it complicates outputting results, but you might call timeval_subtract() with something like below:

    // replace MY_SPECIFIC_PREPROC_8B_DEF with your own 
    //  preprocessor time_t distinguishing define
    #if defined MY_SPECIFIC_PREPROC_8B_DEF
     #define LSPEC "lld"                     // format specifier input length
     char fmt[] = "% 020" LSPEC " % 011ld "; // long long tv_sec"
     #define MAX_TIME_T 0x7fffffffffffffff
     #define MIN_TIME_T 0x8000000000000000
    #else
     #define LSPEC "ld"
     char fmt[] = "% 011" LSPEC " % 011ld "; // less chars for long tv_sec"
     #define MAX_TIME_T 0x7fffffff
     #define MIN_TIME_T 0x80000000
    #endif

    const time_t max_time_t = MAX_TIME_T;
    const time_t min_time_t = MIN_TIME_T;

    // Test overflow of both timeval members, sec & usec
    struct timeval a = {min_time_t, 1};   // 1 usec > negative overflow
    struct timeval b = {0, 0};            // our subtrahend, ++1 usec in loop
    struct timeval c = {0, 0};      // holds result; difference in this case

    strcat (fmt, "= a{%" LSPEC ",%ld} - b{%" LSPEC ",%ld}\n");

    for (auto i=0; i<3; i++) {
        timeval_subtract (&a,&b,&c);
        Serial.printf(fmt,
          c.tv_sec, c.tv_usec, a.tv_sec, a.tv_usec, b.tv_sec, b.tv_usec);
        b.tv_usec += 1;                 // normal time flow
    }

// Without an appropriate preprocessor define this may compile

    for (auto i=0; i<3; i++) {
        timeval_subtract (&a,&b,&c);
        // explicit casts try to quiet compiler on other sized type_t systems
        if (8 == sizeof(time_t)) {
            Serial.printf("% 020lld % 011ld = a{%lld,%ld} - b{%lld,%ld}\n",
                (long long)c.tv_sec, c.tv_usec,
                (long long)a.tv_sec, a.tv_usec,
                (long long)b.tv_sec, b.tv_usec);
        }
        else if (4 == sizeof(time_t)) {
            Serial.printf("% 011ld % 011ld = a{%ld,%ld} - b{%ld,%ld}\n",
                (long)c.tv_sec, c.tv_usec,
                (long)a.tv_sec, a.tv_usec,
                (long)b.tv_sec, b.tv_usec);
        }
        b.tv_usec += 1;                 // normal time flow
    }