poniedziałek, 30 grudnia 2013

I accidentally created an infinite loop

I needed to iterate through all values of 32-bit unsigned integer, so I wrote:


#include <stdint.h>
for (uint32_t i=0; i <= UINT32_MAX; i++) {
   // whatever
}
 
Is it ok? No, because value of uint32_t will never exceed UINT32_MAX = 0xffffffff. Of course we can use larger types, like uint64_t, but on 32-bit machines this requires some additional instructions. For example gcc 4.7 compiled following code:

void loop1(void (*fun)()) {
 for (uint64_t i=0; i <= UINT32_MAX; i++) {
  fun();
 }
}
 
to:

00000000 :
   0:   57                      push   %edi
   1:   bf 01 00 00 00          mov    $0x1,%edi
   6:   56                      push   %esi
   7:   31 f6                   xor    %esi,%esi
   9:   53                      push   %ebx
   a:   8b 5c 24 10             mov    0x10(%esp),%ebx
   e:   66 90                   xchg   %ax,%ax
  10:   ff d3                   call   *%ebx
  12:   83 c6 ff                add    $0xffffffff,%esi
  15:   83 d7 ff                adc    $0xffffffff,%edi
  18:   89 f8                   mov    %edi,%eax
  1a:   09 f0                   or     %esi,%eax
  1c:   75 f2                   jne    10 
  1e:   5b                      pop    %ebx
  1f:   5e                      pop    %esi
  20:   5f                      pop    %edi
  21:   c3                      ret    

TBH, I have no idea, why such weird sequence has been generated (add, adc, or, jnz). The simplest and portable solution is to detect wrap-around 32-bit value after increment:


uint32_t i=0;
while (1) {
 // loop body

 i += 1;
 if (i == 0) // wrap-around
  break;
}

In assembly code it's even simpler, because CPU sets the carry flag:

     xor %eax, %eax
loop:
     ; loop body

     add $1, %eax
     jnc loop