Wednesday, March 21, 2012

ELF File Format

The C++ source code below:


#include <cstdio>
#include <iostream>

using namespace std;

class CParent {
public:
 CParent() {
  ref++;
  cout <<  "class CParent: constructor ref=" << ref << endl;
  Function();
 };
 virtual ~CParent() {
  ref--;
  cout << "class CParent: destructor ref=" << ref << endl;
 }
 virtual int Function() {
  cout << "\tA::Function()" << endl;
  return ref;
 }
 static unsigned int ref;
};


class CChild : public CParent {
public:
 CChild() {
  ref++;
  cout << "\tclass CChild: constructor ref=" << ref << endl;
  m_a = new CParent();
 };
 virtual ~CChild() {
  ref--;
  cout << "\tclass CChild: destructor ref=" << ref << endl;
  delete m_a;
 }

 static unsigned int ref;
private:
 CParent *m_a;
};


unsigned int CParent::ref = 0;
unsigned int CChild::ref = 0;

int main()
{
 int i;
 int n = 2;

 CChild *c = new CChild[n];
 for(i=0; i(&c[i]);
  printf("p[%d].Function()=%d\n", i, p->Function());
 }
 cout << "CChild::Ref=" << CChild::ref << endl;
 delete [] c;
}
A in-depth view of the generated ELF file format from the above C++ code is as below: 


[buhadram@localhost src]$ readelf -a virt
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Intel 80386
  Version:                           0x1
  Entry point address:               0x80487d0
  Start of program headers:          52 (bytes into file)
  Start of section headers:          5192 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           32 (bytes)
  Number of program headers:         8
  Size of section headers:           40 (bytes)
  Number of section headers:         31
  Section header string table index: 28

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08048134 000134 000013 00   A  0   0  1
  [ 2] .note.ABI-tag     NOTE            08048148 000148 000020 00   A  0   0  4
  [ 3] .note.gnu.build-i NOTE            08048168 000168 000024 00   A  0   0  4
  [ 4] .gnu.hash         GNU_HASH        0804818c 00018c 000040 04   A  5   0  4
  [ 5] .dynsym           DYNSYM          080481cc 0001cc 000160 10   A  6   1  4
  [ 6] .dynstr           STRTAB          0804832c 00032c 000214 00   A  0   0  1
  [ 7] .gnu.version      VERSYM          08048540 000540 00002c 02   A  5   0  2
  [ 8] .gnu.version_r    VERNEED         0804856c 00056c 000080 00   A  6   3  4
  [ 9] .rel.dyn          REL             080485ec 0005ec 000020 08   A  5   0  4
  [10] .rel.plt          REL             0804860c 00060c 000080 08   A  5  12  4
  [11] .init             PROGBITS        0804868c 00068c 000030 00  AX  0   0  4
  [12] .plt              PROGBITS        080486bc 0006bc 000110 04  AX  0   0  4
  [13] .text             PROGBITS        080487d0 0007d0 0005dc 00  AX  0   0 16
  [14] .fini             PROGBITS        08048dac 000dac 00001c 00  AX  0   0  4
  [15] .rodata           PROGBITS        08048dc8 000dc8 000114 00   A  0   0  8
  [16] .eh_frame_hdr     PROGBITS        08048edc 000edc 000074 00   A  0   0  4
  [17] .eh_frame         PROGBITS        08048f50 000f50 00022c 00   A  0   0  4
  [18] .gcc_except_table PROGBITS        0804917c 00117c 000041 00   A  0   0  1
  [19] .ctors            PROGBITS        0804a1c0 0011c0 00000c 00  WA  0   0  4
  [20] .dtors            PROGBITS        0804a1cc 0011cc 000008 00  WA  0   0  4
  [21] .jcr              PROGBITS        0804a1d4 0011d4 000004 00  WA  0   0  4
  [22] .dynamic          DYNAMIC         0804a1d8 0011d8 0000e0 08  WA  6   0  4
  [23] .got              PROGBITS        0804a2b8 0012b8 000004 04  WA  0   0  4
  [24] .got.plt          PROGBITS        0804a2bc 0012bc 00004c 04  WA  0   0  4
  [25] .data             PROGBITS        0804a308 001308 000004 00  WA  0   0  4
  [26] .bss              NOBITS          0804a320 00130c 000120 00  WA  0   0 32
  [27] .comment          PROGBITS        00000000 00130c 00002c 01  MS  0   0  1
  [28] .shstrtab         STRTAB          00000000 001338 00010e 00      0   0  1
  [29] .symtab           SYMTAB          00000000 001920 000680 10     30  49  4
  [30] .strtab           STRTAB          00000000 001fa0 0005a2 00      0   0  1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings)
  I (info), L (link order), G (group), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

There are no section groups in this file.

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08048034 0x08048034 0x00100 0x00100 R E 0x4
  INTERP         0x000134 0x08048134 0x08048134 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08048000 0x08048000 0x011bd 0x011bd R E 0x1000
  LOAD           0x0011c0 0x0804a1c0 0x0804a1c0 0x0014c 0x00280 RW  0x1000
  DYNAMIC        0x0011d8 0x0804a1d8 0x0804a1d8 0x000e0 0x000e0 RW  0x4
  NOTE           0x000148 0x08048148 0x08048148 0x00044 0x00044 R   0x4
  GNU_EH_FRAME   0x000edc 0x08048edc 0x08048edc 0x00074 0x00074 R   0x4
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4

 Section to Segment mapping:
  Segment Sections...
   00     
   01     .interp 
   02     .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rel.dyn .rel.plt .init .plt .text .fini .rodata .eh_frame_hdr .eh_frame .gcc_except_table 
   03     .ctors .dtors .jcr .dynamic .got .got.plt .data .bss 
   04     .dynamic 
   05     .note.ABI-tag .note.gnu.build-id 
   06     .eh_frame_hdr 
   07     

Dynamic section at offset 0x11d8 contains 23 entries:
  Tag        Type                         Name/Value
 0x00000001 (NEEDED)                     Shared library: [libstdc++.so.6]
 0x00000001 (NEEDED)                     Shared library: [libm.so.6]
 0x00000001 (NEEDED)                     Shared library: [libgcc_s.so.1]
 0x00000001 (NEEDED)                     Shared library: [libc.so.6]
 0x0000000c (INIT)                       0x804868c
 0x0000000d (FINI)                       0x8048dac
 0x6ffffef5 (GNU_HASH)                   0x804818c
 0x00000005 (STRTAB)                     0x804832c
 0x00000006 (SYMTAB)                     0x80481cc
 0x0000000a (STRSZ)                      532 (bytes)
 0x0000000b (SYMENT)                     16 (bytes)
 0x00000015 (DEBUG)                      0x0
 0x00000003 (PLTGOT)                     0x804a2bc
 0x00000002 (PLTRELSZ)                   128 (bytes)
 0x00000014 (PLTREL)                     REL
 0x00000017 (JMPREL)                     0x804860c
 0x00000011 (REL)                        0x80485ec
 0x00000012 (RELSZ)                      32 (bytes)
 0x00000013 (RELENT)                     8 (bytes)
 0x6ffffffe (VERNEED)                    0x804856c
 0x6fffffff (VERNEEDNUM)                 3
 0x6ffffff0 (VERSYM)                     0x8048540
 0x00000000 (NULL)                       0x0

Relocation section '.rel.dyn' at offset 0x5ec contains 4 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
0804a2b8  00000206 R_386_GLOB_DAT    00000000   __gmon_start__
0804a320  00000f05 R_386_COPY        0804a320   _ZTVN10__cxxabiv117__c
0804a360  00001405 R_386_COPY        0804a360   _ZSt4cout
0804a400  00001005 R_386_COPY        0804a400   _ZTVN10__cxxabiv120__s

Relocation section '.rel.plt' at offset 0x60c contains 16 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
0804a2c8  00000107 R_386_JUMP_SLOT   00000000   __cxa_atexit
0804a2cc  00000207 R_386_JUMP_SLOT   00000000   __gmon_start__
0804a2d0  00000407 R_386_JUMP_SLOT   00000000   _ZdlPv
0804a2d4  00000507 R_386_JUMP_SLOT   00000000   _ZNSt8ios_base4InitC1E
0804a2d8  00000607 R_386_JUMP_SLOT   00000000   __libc_start_main
0804a2dc  00001307 R_386_JUMP_SLOT   0804871c   _ZNSt8ios_base4InitD1E
0804a2e0  00000707 R_386_JUMP_SLOT   00000000   _ZStlsISt11char_traits
0804a2e4  00000807 R_386_JUMP_SLOT   00000000   printf
0804a2e8  00000907 R_386_JUMP_SLOT   00000000   _ZNSolsEj
0804a2ec  00000a07 R_386_JUMP_SLOT   00000000   _Znwj
0804a2f0  00000b07 R_386_JUMP_SLOT   00000000   _Znaj
0804a2f4  00000c07 R_386_JUMP_SLOT   00000000   _ZdaPv
0804a2f8  00000d07 R_386_JUMP_SLOT   00000000   _ZNSolsEPFRSoS_E
0804a2fc  00001207 R_386_JUMP_SLOT   0804879c   _ZSt4endlIcSt11char_tr
0804a300  00001507 R_386_JUMP_SLOT   080487ac   __gxx_personality_v0
0804a304  00000e07 R_386_JUMP_SLOT   00000000   _Unwind_Resume

There are no unwind sections in this file.

Symbol table '.dynsym' contains 22 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 00000000     0 FUNC    GLOBAL DEFAULT  UND __cxa_atexit@GLIBC_2.1.3 (2)
     2: 00000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
     3: 00000000     0 NOTYPE  WEAK   DEFAULT  UND _Jv_RegisterClasses
     4: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZdlPv@GLIBCXX_3.4 (3)
     5: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZNSt8ios_base4InitC1Ev@GLIBCXX_3.4 (3)
     6: 00000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.0 (4)
     7: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZStlsISt11char_traitsIcE@GLIBCXX_3.4 (3)
     8: 00000000     0 FUNC    GLOBAL DEFAULT  UND printf@GLIBC_2.0 (4)
     9: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZNSolsEj@GLIBCXX_3.4 (3)
    10: 00000000     0 FUNC    GLOBAL DEFAULT  UND _Znwj@GLIBCXX_3.4 (3)
    11: 00000000     0 FUNC    GLOBAL DEFAULT  UND _Znaj@GLIBCXX_3.4 (3)
    12: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZdaPv@GLIBCXX_3.4 (3)
    13: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZNSolsEPFRSoS_E@GLIBCXX_3.4 (3)
    14: 00000000     0 FUNC    GLOBAL DEFAULT  UND _Unwind_Resume@GCC_3.0 (6)
    15: 0804a320    44 OBJECT  WEAK   DEFAULT   26 _ZTVN10__cxxabiv117__clas@CXXABI_1.3 (5)
    16: 0804a400    44 OBJECT  WEAK   DEFAULT   26 _ZTVN10__cxxabiv120__si_c@CXXABI_1.3 (5)
    17: 08048dcc     4 OBJECT  GLOBAL DEFAULT   15 _IO_stdin_used
    18: 0804879c     0 FUNC    GLOBAL DEFAULT  UND _ZSt4endlIcSt11char_trait@GLIBCXX_3.4 (3)
    19: 0804871c     0 FUNC    GLOBAL DEFAULT  UND _ZNSt8ios_base4InitD1Ev@GLIBCXX_3.4 (3)
    20: 0804a360   140 OBJECT  GLOBAL DEFAULT   26 _ZSt4cout@GLIBCXX_3.4 (3)
    21: 080487ac     0 FUNC    GLOBAL DEFAULT  UND __gxx_personality_v0@CXXABI_1.3 (5)

Symbol table '.symtab' contains 104 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 08048134     0 SECTION LOCAL  DEFAULT    1 
     2: 08048148     0 SECTION LOCAL  DEFAULT    2 
     3: 08048168     0 SECTION LOCAL  DEFAULT    3 
     4: 0804818c     0 SECTION LOCAL  DEFAULT    4 
     5: 080481cc     0 SECTION LOCAL  DEFAULT    5 
     6: 0804832c     0 SECTION LOCAL  DEFAULT    6 
     7: 08048540     0 SECTION LOCAL  DEFAULT    7 
     8: 0804856c     0 SECTION LOCAL  DEFAULT    8 
     9: 080485ec     0 SECTION LOCAL  DEFAULT    9 
    10: 0804860c     0 SECTION LOCAL  DEFAULT   10 
    11: 0804868c     0 SECTION LOCAL  DEFAULT   11 
    12: 080486bc     0 SECTION LOCAL  DEFAULT   12 
    13: 080487d0     0 SECTION LOCAL  DEFAULT   13 
    14: 08048dac     0 SECTION LOCAL  DEFAULT   14 
    15: 08048dc8     0 SECTION LOCAL  DEFAULT   15 
    16: 08048edc     0 SECTION LOCAL  DEFAULT   16 
    17: 08048f50     0 SECTION LOCAL  DEFAULT   17 
    18: 0804917c     0 SECTION LOCAL  DEFAULT   18 
    19: 0804a1c0     0 SECTION LOCAL  DEFAULT   19 
    20: 0804a1cc     0 SECTION LOCAL  DEFAULT   20 
    21: 0804a1d4     0 SECTION LOCAL  DEFAULT   21 
    22: 0804a1d8     0 SECTION LOCAL  DEFAULT   22 
    23: 0804a2b8     0 SECTION LOCAL  DEFAULT   23 
    24: 0804a2bc     0 SECTION LOCAL  DEFAULT   24 
    25: 0804a308     0 SECTION LOCAL  DEFAULT   25 
    26: 0804a320     0 SECTION LOCAL  DEFAULT   26 
    27: 00000000     0 SECTION LOCAL  DEFAULT   27 
    28: 00000000     0 FILE    LOCAL  DEFAULT  ABS crtstuff.c
    29: 0804a1c0     0 OBJECT  LOCAL  DEFAULT   19 __CTOR_LIST__
    30: 0804a1cc     0 OBJECT  LOCAL  DEFAULT   20 __DTOR_LIST__
    31: 0804a1d4     0 OBJECT  LOCAL  DEFAULT   21 __JCR_LIST__
    32: 08048800     0 FUNC    LOCAL  DEFAULT   13 __do_global_dtors_aux
    33: 0804a42c     1 OBJECT  LOCAL  DEFAULT   26 completed.5530
    34: 0804a430     4 OBJECT  LOCAL  DEFAULT   26 dtor_idx.5532
    35: 08048860     0 FUNC    LOCAL  DEFAULT   13 frame_dummy
    36: 00000000     0 FILE    LOCAL  DEFAULT  ABS crtstuff.c
    37: 0804a1c8     0 OBJECT  LOCAL  DEFAULT   19 __CTOR_END__
    38: 08049178     0 OBJECT  LOCAL  DEFAULT   17 __FRAME_END__
    39: 0804a1d4     0 OBJECT  LOCAL  DEFAULT   21 __JCR_END__
    40: 08048d80     0 FUNC    LOCAL  DEFAULT   13 __do_global_ctors_aux
    41: 00000000     0 FILE    LOCAL  DEFAULT  ABS virt.cpp
    42: 0804a43c     1 OBJECT  LOCAL  DEFAULT   26 _ZStL8__ioinit
    43: 08048a08    64 FUNC    LOCAL  DEFAULT   13 _Z41__static_initializati
    44: 08048a48    28 FUNC    LOCAL  DEFAULT   13 _GLOBAL__I__ZN7CParent3re
    45: 0804a2bc     0 OBJECT  LOCAL  DEFAULT   24 _GLOBAL_OFFSET_TABLE_
    46: 0804a1bd     0 NOTYPE  LOCAL  DEFAULT   19 __init_array_end
    47: 0804a1bd     0 NOTYPE  LOCAL  DEFAULT   19 __init_array_start
    48: 0804a1d8     0 OBJECT  LOCAL  DEFAULT   22 _DYNAMIC
    49: 0804a308     0 NOTYPE  WEAK   DEFAULT   25 data_start
    50: 00000000     0 FUNC    GLOBAL DEFAULT  UND __cxa_atexit@@GLIBC_2.1.3
    51: 08048d70     5 FUNC    GLOBAL DEFAULT   13 __libc_csu_fini
    52: 080487d0     0 FUNC    GLOBAL DEFAULT   13 _start
    53: 08048ebc    12 OBJECT  WEAK   DEFAULT   15 _ZTI6CChild
    54: 00000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
    55: 00000000     0 NOTYPE  WEAK   DEFAULT  UND _Jv_RegisterClasses
    56: 08048dc8     4 OBJECT  GLOBAL DEFAULT   15 _fp_hw
    57: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZdlPv@@GLIBCXX_3.4
    58: 0804a434     4 OBJECT  GLOBAL DEFAULT   26 _ZN7CParent3refE
    59: 08048dac     0 FUNC    GLOBAL DEFAULT   14 _fini
    60: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZNSt8ios_base4InitC1Ev@@
    61: 00000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@@GLIBC_
    62: 08048e88    20 OBJECT  WEAK   DEFAULT   15 _ZTV6CChild
    63: 08048b56    49 FUNC    WEAK   DEFAULT   13 _ZN7CParent8FunctionEv
    64: 08048cea    30 FUNC    WEAK   DEFAULT   13 _ZN6CChildD0Ev
    65: 08048b88   171 FUNC    WEAK   DEFAULT   13 _ZN6CChildC2Ev
    66: 0804871c     0 FUNC    GLOBAL DEFAULT  UND _ZNSt8ios_base4InitD1Ev@@
    67: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZStlsISt11char_traitsIcE
    68: 08048dcc     4 OBJECT  GLOBAL DEFAULT   15 _IO_stdin_used
    69: 0804a308     0 NOTYPE  GLOBAL DEFAULT   25 __data_start
    70: 0804a320    44 OBJECT  WEAK   DEFAULT   26 _ZTVN10__cxxabiv117__clas
    71: 0804a360   140 OBJECT  GLOBAL DEFAULT   26 _ZSt4cout@@GLIBCXX_3.4
    72: 08048dd0     0 OBJECT  GLOBAL HIDDEN    15 __dso_handle
    73: 0804a1d0     0 OBJECT  GLOBAL HIDDEN    20 __DTOR_END__
    74: 08048d10    90 FUNC    GLOBAL DEFAULT   13 __libc_csu_init
    75: 00000000     0 FUNC    GLOBAL DEFAULT  UND printf@@GLIBC_2.0
    76: 08048a64   100 FUNC    WEAK   DEFAULT   13 _ZN7CParentC2Ev
    77: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZNSolsEj@@GLIBCXX_3.4
    78: 08048ac8   112 FUNC    WEAK   DEFAULT   13 _ZN7CParentD1Ev
    79: 00000000     0 FUNC    GLOBAL DEFAULT  UND _Znwj@@GLIBCXX_3.4
    80: 00000000     0 FUNC    GLOBAL DEFAULT  UND _Znaj@@GLIBCXX_3.4
    81: 08048a64   100 FUNC    WEAK   DEFAULT   13 _ZN7CParentC1Ev
    82: 08048ed4     8 OBJECT  WEAK   DEFAULT   15 _ZTI7CParent
    83: 08048b38    30 FUNC    WEAK   DEFAULT   13 _ZN7CParentD0Ev
    84: 08048c34   182 FUNC    WEAK   DEFAULT   13 _ZN6CChildD2Ev
    85: 0804a30c     0 NOTYPE  GLOBAL DEFAULT  ABS __bss_start
    86: 0804a400    44 OBJECT  WEAK   DEFAULT   26 _ZTVN10__cxxabiv120__si_c
    87: 0804a438     4 OBJECT  GLOBAL DEFAULT   26 _ZN6CChild3refE
    88: 08048ec8     9 OBJECT  WEAK   DEFAULT   15 _ZTS7CParent
    89: 08048ac8   112 FUNC    WEAK   DEFAULT   13 _ZN7CParentD2Ev
    90: 08048eb4     8 OBJECT  WEAK   DEFAULT   15 _ZTS6CChild
    91: 08048ea0    20 OBJECT  WEAK   DEFAULT   15 _ZTV7CParent
    92: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZdaPv@@GLIBCXX_3.4
    93: 0804a440     0 NOTYPE  GLOBAL DEFAULT  ABS _end
    94: 00000000     0 FUNC    GLOBAL DEFAULT  UND _ZNSolsEPFRSoS_E@@GLIBCXX
    95: 08048b88   171 FUNC    WEAK   DEFAULT   13 _ZN6CChildC1Ev
    96: 0804879c     0 FUNC    GLOBAL DEFAULT  UND _ZSt4endlIcSt11char_trait
    97: 0804a30c     0 NOTYPE  GLOBAL DEFAULT  ABS _edata
    98: 08048c34   182 FUNC    WEAK   DEFAULT   13 _ZN6CChildD1Ev
    99: 080487ac     0 FUNC    GLOBAL DEFAULT  UND __gxx_personality_v0@@CXX
   100: 00000000     0 FUNC    GLOBAL DEFAULT  UND _Unwind_Resume@@GCC_3.0
   101: 08048d75     0 FUNC    GLOBAL HIDDEN    13 __i686.get_pc_thunk.bx
   102: 08048884   388 FUNC    GLOBAL DEFAULT   13 main
   103: 0804868c     0 FUNC    GLOBAL DEFAULT   11 _init

Histogram for `.gnu.hash' bucket list length (total of 3 buckets):
 Length  Number     % of total  Coverage
      0  0          (  0.0%)
      1  0          (  0.0%)      0.0%
      2  2          ( 66.7%)     57.1%
      3  1          ( 33.3%)    100.0%

Version symbols section '.gnu.version' contains 22 entries:
 Addr: 0000000008048540  Offset: 0x000540  Link: 5 (.dynsym)
  000:   0 (*local*)       2 (GLIBC_2.1.3)   0 (*local*)       0 (*local*)    
  004:   3 (GLIBCXX_3.4)   3 (GLIBCXX_3.4)   4 (GLIBC_2.0)     3 (GLIBCXX_3.4)
  008:   4 (GLIBC_2.0)     3 (GLIBCXX_3.4)   3 (GLIBCXX_3.4)   3 (GLIBCXX_3.4)
  00c:   3 (GLIBCXX_3.4)   3 (GLIBCXX_3.4)   6 (GCC_3.0)       5 (CXXABI_1.3) 
  010:   5 (CXXABI_1.3)    1 (*global*)      3 (GLIBCXX_3.4)   3 (GLIBCXX_3.4)
  014:   3 (GLIBCXX_3.4)   5 (CXXABI_1.3) 

Version needs section '.gnu.version_r' contains 3 entries:
 Addr: 0x000000000804856c  Offset: 0x00056c  Link: 6 (.dynstr)
  000000: Version: 1  File: libgcc_s.so.1  Cnt: 1
  0x0010:   Name: GCC_3.0  Flags: none  Version: 6
  0x0020: Version: 1  File: libstdc++.so.6  Cnt: 2
  0x0030:   Name: CXXABI_1.3  Flags: none  Version: 5
  0x0040:   Name: GLIBCXX_3.4  Flags: none  Version: 3
  0x0050: Version: 1  File: libc.so.6  Cnt: 2
  0x0060:   Name: GLIBC_2.0  Flags: none  Version: 4
  0x0070:   Name: GLIBC_2.1.3  Flags: none  Version: 2

Notes at offset 0x00000148 with length 0x00000020:
  Owner  Data size Description
  GNU  0x00000010 NT_GNU_ABI_TAG (ABI version tag)

Notes at offset 0x00000168 with length 0x00000024:
  Owner  Data size Description
  GNU  0x00000014 NT_GNU_BUILD_ID (unique build ID bitstring)
[buhadram@localhost src]$
Posted by at No comments:

Friday, March 16, 2012

Google Interview (3)

Question:
How would you reverse the image on an n by n matrix where each pixel is represented by a bit?

Answer:
I: n x n matrix
I[0][0] represents 1 byte at the left-most, top-most corner (8 pixels).

Just image it as columns and rows of pixels.  For example, a line of an image is represented on the screen as columns of pixels:

+----+----+----+ ....+-----+-----+---+
| p1 | p2 | p3 |     |pm-2  | pm-1| pm |
+----+----+----+ ....+-----+-----+---+




In reversed image, it looks like below:






+---+----+----+ ....+----+----+----+
|pm |pm-1 |pm-2|     | p3 | p2 | p1 |
+---+----+----+ ....+----+----+----+








The reverse version would have the column position reversed as well as the bit order in each bit. To do this, we need to read each row of the original image in reverse and also do bit reversal.



We have to be careful when swapping bytes above.  On 32-bit computers, we can swap left-right of every 32-bit integer of columns, or on 64-bit PCs we can do 64-bit (long integer) swapping before doing the bit reverse.



For example:



n = m/(sizeof(long integer)

for i=0 to n

    right_idx = m-1-i;

    swapLongInteger(image[i], image[right_idx]) 

    Reverse8Bit(image[i])

    Reverse8Bit(image[i+1])

    Reverse8Bit(image[i+2]) 

    Reverse8Bit(image[i+3])  

    Reverse8Bit(image[right_idx])

    Reverse8Bit(image[right_idx-1])

    Reverse8Bit(image[right_idx-2])

    Reverse8Bit(image[right_idx-3]) 

    i = i + sizeof(long integer)

done



The call to multiple "Reverse8Bit" above can be put in multithreading/can be done using parallelism to speed up computation.



The pseudo-code is as below:




# I : list original image
# R : reversed image
for i in range(0,n):
    for j in range(0,n):
        R[i][j] = Reverse8Bit(I[i][n-1-j]) 




The Reverse8Bit() function is like below (from http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious):






unsigned int v;     // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{   
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero













Posted by



at





No comments:
  











































          

        

          

        

Thursday, March 15, 2012


          

        









Google Interview (2)










Question:

How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?




Answer:

The stupid and quick answer would be 0 degree.



But, if we rethink again, it's not the case exactly.  When the minute  hand points to '15' (quarter), the hour hand has moved little bit.  How many? Let's analyze!



To make a full-circle (360 degrees rotation), the hour hand has to pass 12 hours, thus for one hour, it takes 360 degrees/12 = 30 degrees.  For a quarter hour = 1/4 * 30 = 7.5 degrees.



So the answer is: 7.5 degrees.









Posted by



at





No comments:
  
















































A Google Interview










Question:

If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers?



Answer:

Let's analyze this.



On a handset, there are keys with number '0' to '9'.  Assume we have to key in full phone number (area code + number),  it's gonna be 10 digits.  Only certain keys have alphabets: 2 [ABC], 3 [DEF], 4 [GHI], 5 [JKL], 6 [MNO], 7 [PQRS], 8 [WXYZ], with total number of sets = 8. The question is to find what is the total number of permutation of these 10-digits out of n set of possible phone numbers



Using permutation formula:








Formula:


 Note: , where nPr is the formula for permutations of n objects taken r at a time.






The set of possible numbers then is: [222-222-2222 to 888-888-8888] or 6,666,666,666 possible phone numbers.



We then compute:

n = 10,000,000,000

r = 10



Permutation =6,666,666,666 !/(10!(6,666,666,666  - 10)!) = (6,666,666,656 * 6,666,666,657 * 6,666,666,658 *6,666,666,669 * 6,666,666,660 * 6,666,666,661 * 6,666,666,662 * 6,666,666,663 * 6,666,666,664 * 6,666,666,665 * 6,666,666,666)/3628800 = <just figure out your self!>



If the allowed valid number is only 1 digit, then computation would be easier:



Permutation = 6,666,666,666!/(1!*(6,666,666,666-1)!) = 6,666,666,666 possible words














Posted by



at





No comments:
  















































Fast Hashing of Variable-length text strings










The following Hash algorithm based on a research paper written by Peter Pearson (a scientist at Lawrence Livermore National Lab) has an ability to generate unique hash numbers for strings with lengths no longer than 256 bytes.  That means, we can have up to 256 buckets in a hash table, but it guarantees the uniqueness (free of hash-collision), thus no need to have linked-list in buckets.





The beauty of this algorithm is that it is designed to work on small microprocessors or microcontrollers, which sometimes don't have luxury to do complex arithmetics in their Instruction set (or, require more instructions).  Instead, the following algorithm uses XOR and table lookup which should be easy to do in small CPUs.  On more modern and high-end CPUs, XOR operation translated directly to mnemonic XOR in machine-code (a single instruction) and done even in almost wire-speed.



One of the use I can think of is for creating MAC table for virtual bridging.  An Ethernet MAC address takes only 6 octets, so this algorithm can be used to lookup 256-bucket MAC table.  The hash-key is MACaddr, while the output is port.



For example:



A MAC table structure might look like below:


+-------------------+---------+------+
|      MACAddr      +  port   |  Age |
+-------------------+---------+------+
| XX:XX:XX:XX:XX:XX |    1    |  6   |
| YY:YY:YY:YY:YY:YY |    2    |  7   |
| ZZ:ZZ:ZZ:ZZ:ZZ:ZZ |    3    |  102 |
| AA:BB:BB:BB:BB:BB |    4    |  33  |
| AA:AA:AA:AA:AA:AA |    5    |  76  |
+-------------------+---------+------+




Learning:

port = PearsonHash(SourceMacAddr);

MACTable[port].addr = SourceMacAddr;

MACTable[port].port = port;



Forwarding:

inspect destination MAC address from incoming ethernet frame



//Flooding

if (DestMacAddr == Broadcast)

      Send to all ports, except the original incoming port, with this frame



// a small filtering is done here to prevent loop

if (DestMacAddr != SourceMacAddr)

{

     port = PearsonHash(DestMacAddr);

     if port is invalid:

          flooding

     else

     DataForward(EthernetFrame, port);

}



Aging:

The following statements can be executed periodically.



for each entry/bucket in the MAC table:

      if MACTable[i].age < 1:

            Flush(MACTable[i])



A challenge might be how to expand this algorithm to handle, say, 64000 buckets/entries?  How to generate the pseudorandom hash table?




#include <stdio.h>
#include <string.h>
#include <stdlib.h>


static unsigned char PseudoRandomHash[256] = {
     1,   87,   49,  12, 176, 178,  102, 166, 121, 193,   6,  84, 249, 230,  44,  163, 
     14, 197,  213, 181, 161,  85,  218,  80,  64, 239,  24, 226, 236, 142,  38,  200, 
    110, 177,  104, 103, 141, 253,  255,  50,  77, 101,  81,  18,  45,  96,  31,  222, 
     25, 107,  190,  70,  86, 237,  240,  34,  72, 242,  20, 214, 244, 227, 149,  235, 
     97, 234,   57,  22,  60, 250,   82,  175, 208,   5, 127, 199, 111,  62, 135,  248, 
    174, 169,  211,  58,  66, 154,  106, 195, 245, 171,  17, 187, 182, 179,   0,  243, 
    132,  56,  148,  75, 128, 133,  158, 100, 130, 126,  91,  13, 153, 246, 216,  219,
    119,  68,  223,  78,  83,  88,  201,  99, 122,  11,  92,  32, 136, 114,  52,   10, 
    138,  30,   48, 183, 156,  35,   61,  26, 143,  74, 251,  94, 129, 162,  63,  152, 
    170,   7,  115, 167, 241, 206,    3, 150,  55,  59, 151, 220,  90,  53,  23,  131, 
    125, 173,   15, 238,  79,  95,   89,  16, 105, 137, 225, 224, 217, 160,  37,  123, 
    118,  73,    2, 157,  46, 116,    9, 145, 134, 228, 207, 212, 202, 215,  69,  229, 
     27, 188,   67, 124, 168, 252,   42,   4,  29, 108,  21, 247,  19, 205,  39,  203, 
    233,  40,  186, 147, 198, 192,  155,  33, 164, 191,  98, 204, 165, 180, 117,   76, 
    140,  36,  210, 172,  41,  54,  159,   8, 185, 232, 113, 196, 231,  47, 146,  120, 
     51,  65,   28, 144, 254, 221,   93, 189, 194, 139, 112,  43,  71, 109, 184,  209}; 
     
#define N   256
     
     
int PearsonHash(const char *str)
{
    int n = strlen(str);
    int i;
    unsigned char *h;
    int result;
    
    if (n > N)
    {
        puts("Pearson Hashing can only be used for string length <256 characters");
        return -1;
    }
    h = (unsigned char *)malloc(N);
    bzero(h, sizeof(char)*N);
    h[0] = 0;
    for(i=1; i<n; i++)
    {
        h[i] = PseudoRandomHash[(h[i-1] ^ str[i])& 0xFF];
        //printf("h[%u]=%0x\n", i, h[i]);
        result = h[i];
    }
    free(h);
    return result;
}

     
int main()
{
    int i;
    int n;
    const char MyStringBase[] = "Ahlan Wa Sahlan Bib, ";
    char *StrTable[N];
    
    for(i=0; i<N; i++)
    {
        printf(" %03u ", PseudoRandomHash[i]);
        if ((i+1)%16 == 0)
            printf("\n");
    }
    for(i=0; i<N; i++)
    {
        StrTable[i] = (char *)malloc(N);
        sprintf(StrTable[i], "%s%u", MyStringBase, i);
    }    
    for(i=0; i<N; i++)
    {
        printf("\n%s: \tHash Index=%u\n", StrTable[i], PearsonHash(StrTable[i]));
        free(StrTable[i]);
    }    
}     











Posted by



at





2 comments:
  







































          

        

          

        

Wednesday, March 14, 2012


          

        









Print Canonical Addresses of a Site










This 2 lines of Python queries DNS and display the canonical names of a host.  It's like a simple DNS lookup (nslookup).




#!/usr/bin/python

import sys
import socket

HOST=''
PORT=80

if (len(sys.argv) < 2):
 print sys.argv[0], " "
 sys.exit(0)

HOST = sys.argv[1]
for res in socket.getaddrinfo(HOST, PORT, socket.AF_UNSPEC, socket.SOCK_STREAM):
   print res[4][0]








For example, if we execute the script and pass parameter 'www.google.com', we'd get this:






$ ./getdns.py www.google.com
74.125.224.50
74.125.224.51
74.125.224.48
74.125.224.49
74.125.224.52













Posted by



at





No comments:
  







































        

      









Subscribe to:
Posts (Atom)