c - timeval_subtract explanation -

with "timeval_subtract" function find time elapsed between 2 struct timeval types, can please explain purpose of , step step maths used "perform carry later subtraction updating y" , other sections? understand purpose of function , how implement within program, understand how works inside , cannot find explanations of anywhere, , can't seem wrap head around it.

int timeval_subtract (struct timeval *result, struct timeval *x,struct timeval  *y)   {     /* perform carry later subtraction 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 time remaining wait.      tv_usec positive. */     result->tv_sec = x->tv_sec - y->tv_sec;     result->tv_usec = x->tv_usec - y->tv_usec;      /* return 1 if result negative. */     return x->tv_sec < y->tv_sec;   } 

it function described in relation gnu c library determining elapsed time http://www.gnu.org/software/libc/manual/html_node/elapsed-time.html not looking improvements explanation of why dividing , adding , subtracting , multiplying within it. these specific arithmetic operations achieve?/why done/not done? have done stepping through still can'y head around it. continue until (and after explains me) hoping insight understands already. platform unix, new using, don't think changes operations taking place inside function. more question arithmetic being performed algorithm being used.

at first glance, looks struct timeval contains time split 2 parts:

• tv_usec - microseconds, ideally should under 1000000, greater values seem allowed suggested code
• tv_sec - seconds (the number of multiples of 1000000)

and time in microseconds tv_usec + tv_sec * 1000000.

conversely, 1 expect true:

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

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

a simple test program gives 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 carry later subtraction 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 time remaining wait.      tv_usec positive. */     result->tv_sec = x->tv_sec - y->tv_sec;     result->tv_usec = x->tv_usec - y->tv_usec;      /* return 1 if result 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 last test result appears function returns (-1):999999 instead of -(0:1). both values represent same negative time (or time difference) in microseconds:

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

so, how work?

if x->tv_usec >= y->tv_usec second if 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 difference in microseconds parts alone greater 1 second. if is, subtracts whole seconds of difference y->tv_usec (as microseconds) , adds y->tv_sec (as seconds). redistributes time in *y without changing it. rewrite if equivalently see 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 note here when input *x , *y have tv_usec in range 0 999999 inclusive, body of if not execute (hence, probably^* never when x->tv_usec >= y->tv_usec , when tv_usecs in range 0 999999).

the net effect of if not readily clear now.

however, 1 interesting thing can seen here. if call function *x = 0:1000001 , *y = 0:0, result going wrong: difference = (-1):2000001 (instead of 1:1) , return value of function = 1 (instead of 0). suggests function isn't suited tv_usec > 1000000 , tv_usec > 999999. , because of behavior i'm going claim function isn't suited negative tv_usec in inputs either. i'm going ignore cases in face of behavior. looks wrong enough already.

let's @ first if.

  /* perform carry later subtraction 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 comment , code suggests, when x->tv_usec < y->tv_usec need take care of "carry" between "digits" if adding , not subtracting. it's ok, we'll see it.

let's go school moment.

how do 37 - 12?

you this:

7 - 2 = 5 3 - 1 = 2 

and 37 - 12 = 25.

now, how do 57 - 38?

you this:

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

and 57 - 38 = 19. see?

and check:

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

checks whether or not need take care of borrowing.

so, what's happening here? let's 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, calculates difference between 2 in whole seconds , other if adds these whole seconds y->tv_sec , subtracts them y->tv_usec, redistributing time in *y, without changing it.

the 1 (+ 1) ends added y->tv_sec here subtracted x->tv_sec @ end of function (result->tv_sec = x->tv_sec - y->tv_sec;) , 1 functions borrow reminded of in 57 - 38 = 19 example.

what else happening here besides borrow , time redistribution?

like said earlier, i'm going ignore negative tv_usecs , greater 999999 handled incorrectly.

with take (y->tv_usec - x->tv_usec) / 1000000 0 , left meaningful values of tv_usecs (0 999999 inclusive).

so, if if's condition true, subtract 1000000 y->tv_usec , add 1 (the borrow) y->tv_sec.

this same thing had in 57 - 38 = 19:

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

similarly 10, 1000000 going added later in here: result->tv_usec = x->tv_usec - y->tv_usec;

and first if meat of function.

if had write function similar behavior, i'd require input times non-negative , microsecond parts no greater 999999 , i'd write 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 odd reason wanted support tv_usec > 999999 in inputs, i'd first move excess tv_usec tv_sec , above, 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, intent clear , code easy understand.