Random Number Generators

This is an article after my own heart.  Due to my modeling and cryptography work, I've spent a lot of time studying random number generators.  The biggest problem with RNG's is there are two camps: the academic ones that freak out if the initial source of entropy isn't 100% entirely random and well thought out and those that are more practical about the issue and focus more on the algorithm being correct and performing well.  You can go browse the Linux Kernel Mailing list to see this in action.

Parallel Memory Subtley

Found this interesting article in Dr. Dobbs about how memory hardware can impact parallel algorithms. 

First Post: Fun with Compilers

For the first post on my new blog, I thought I'd be random and show what happens when you take the same small piece of code and compile it with both gcc and g++.  You might be surprised that, while identical for the most part, there are some small differences in the assembly code output when targeting for C and C++.

The test program was the same for both compilers, except I saved it as both main.c and main.cpp. Note that I could have kept the same file but I was lazy and didn't feel like forcing the compiler to output pure C code (gcc will compile for C++ when it sees a .cpp extension).


   int main(int argc, char* argv[])
   {
     int i = 0;
     int loop;
  
     for (loop = 0; loop < 50; loop++)
       ++i;


     return 0;
   }

A quick gcc main.c -o main_c and g++ main.cpp -o main_cpp took care of the output.  After that, I used objdump -DCslx -M intel to fully disassemble the programs.

Ignoring the differences (for now) in the ELF output, we examine the main functions in assembler.

Output using gcc:

8048394 <main>:
main():
 8048394: 55                   push   ebp
 8048395: 89 e5                 mov    ebp,esp
 8048397: 83 ec 10             sub    esp,0x10
 804839a: c7 45 fc 00 00 00 00 mov    DWORD PTR [ebp-0x4],0x0
 80483a1: c7 45 f8 00 00 00 00 mov    DWORD PTR [ebp-0x8],0x0
 80483a8: eb 08                 jmp    80483b2 <main+0x1e>
 80483aa: 83 45 fc 01           add    DWORD PTR [ebp-0x4],0x1
 80483ae: 83 45 f8 01           add    DWORD PTR [ebp-0x8],0x1
 80483b2: 83 7d f8 31           cmp    DWORD PTR [ebp-0x8],0x31
 80483b6: 7e f2                 jle    80483aa <main+0x16>
 80483b8: b8 00 00 00 00       mov    eax,0x0
 80483bd: c9                   leave  
 80483be: c3                   ret    
 80483bf: 90                   nop


Output using g++:
080483f4 <main>:

main():
 80483f4: 55                   push   ebp
 80483f5: 89 e5                 mov    ebp,esp
 80483f7: 83 ec 10             sub    esp,0x10
 80483fa: c7 45 fc 00 00 00 00 mov    DWORD PTR [ebp-0x4],0x0
 8048401: c7 45 f8 00 00 00 00 mov    DWORD PTR [ebp-0x8],0x0
 8048408: eb 08                 jmp    8048412 <main+0x1e>
 804840a: 83 45 fc 01           add    DWORD PTR [ebp-0x4],0x1
 804840e: 83 45 f8 01           add    DWORD PTR [ebp-0x8],0x1
 8048412: 83 7d f8 31           cmp    DWORD PTR [ebp-0x8],0x31
 8048416: 0f 9e c0             setle  al
 8048419: 84 c0                 test   al,al
 804841b: 75 ed                 jne    804840a <main+0x16>
 804841d: b8 00 00 00 00       mov    eax,0x0
 8048422: c9                   leave  
 8048423: c3                   ret    
 8048424: 90                   nop
 8048425: 90                   nop
 8048426: 90                   nop
 8048427: 90                   nop
 8048428: 90                   nop
 8048429: 90                   nop
 804842a: 90                   nop
 804842b: 90                   nop
 804842c: 90                   nop
 804842d: 90                   nop
 804842e: 90                   nop
 804842f: 90                   nop



The first part of main() from both C and C++ targeted code is the same.  We'll go through it here to discuss what is happening for those who are more familiar with higher-level languages than Intel x86 assembly.  These lines are pretty much standard for any subroutine in assembly language across different compilers.  They set up a the new stack frame for the subroutine and save pointers from the old routine so it can be recovered upon exiting.


   push   ebp      Push the base pointer to the stack
   mov    ebp,esp  Base and top of stack pointer equal
   sub    esp,0x10 Allocate space for local variables in our new stack frame.



Now we get to the meat of the program.  If you'll recall, I had two local variables in the program declared as:


     int i = 0;
     int loop;


In the assembler output, both the variables (referenced through their aliases on the stack) are initialized to zero.


  mov    DWORD PTR [ebp-0x4],0x0 - explicity set to zero
  mov    DWORD PTR [ebp-0x8],0x0 - gcc sets loop to zero implicity


We then jump to the comparison line where we test that loop (again referenced off the stack) is compared to the value 49 (0x31 in hex).  This is where we see the differences in the output from targeting pure C vs. C++.  I'll copy them below from both the C and C++ target since I've scrolled quite a bit from up top ;)

Loop in C target:

  jmp    80483b2 <main+0x1e>
  add    DWORD PTR [ebp-0x4],0x1
  add    DWORD PTR [ebp-0x8],0x1
  cmp    DWORD PTR [ebp-0x8],0x31
  jle    80483aa <main+0x16>

Loop in C++ target:

  jmp    8048412 <main+0x1e>
  add    DWORD PTR [ebp-0x4],0x1
  add    DWORD PTR [ebp-0x8],0x1
  cmp    DWORD PTR [ebp-0x8],0x31
  setle  al
  test   al,al
  jne    804840a <main+0x16>


Now for the most part they're identical except for how we do our test to break out of the loop.  In the C version, gcc uses the jle (jump if less than or equal) instruction after the comparison (cmp) to go up and add one to i and loop.  In the C++ version, we first use setle (Set if less than or equal) to set the al register to 1 if the comparison matched.  We then test if al is true and then we  use jne to move back up in the function to do the additions.  Once loop is equal to 49, we then put 0 into the EAX register and then exit the routine.

Until I go into WHY there's this slight difference in output, for now let's just say that gcc and g++ use some similar and some different code paths when generating machine code.  Have fun and Happy Father's Day everyone.