#include <map>
#include <iostream>
#include <cstring>
using namespace std;
struct eqstr {
bool operator() (const char *s1, const char *s2) const {
return (::strcmp(s1, s2) < 0 ? true : false);
}
};
int main()
{
// template
map <const char *, int, eqstr> months;
months["january"] = 31;
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;
cout << "february -> " << months["february"] << endl;
cout << "september -> " << months["september"] << endl;
cout << "april -> " << months["april"] << endl;
cout << "july -> " << months["july"] << endl;
cout << "november -> " << months["november"] << endl;
for(map::iterator it=months.begin();
it != months.end(); it++)
{
cout << (*it).first << " => " << (*it).second << endl;
}
}
Friday, March 23, 2012
Hash template in C++
Wednesday, March 21, 2012
ELF File Format
The C++ source code below:
A in-depth view of the generated ELF file format from the above C++ code is as 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;
}
[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]$
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:
In reversed image, it looks like below:
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:
The Reverse8Bit() function is like below (from http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious):
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
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.
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.
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:
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
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
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:
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?
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]);
}
}
Subscribe to:
Posts (Atom)