Algorithms, Theory, Spirituality, Life, Technology, Food and Workout : trying to sort these deterministically in $\Theta(1)$ time (constant time).
Wednesday, May 31, 2006
Gives some solace.....
I have been thinking that I have reinvented the wheel, I had that guilty feeling when I did'nt use _etext , _edata , _end to figure out the begining and end of .data and .bss sections, which I rather got from the ELF sections.
I had a feeling that I reinvented the wheel until I tested the code with _etext , _edata and _end they seem just SCREW....My method was and elite one I love it...I'am really happy. I love it.
Now I realize how its a different feeling when you do things really right from your heart, other day after my workout (obviously with a lot of sweat, I generally jog for 33minutes cover 3 miles and burn 500 CAL) I was talking to arindam. I really liked what this guy said. He said "Workout spirit is something you need to get right from your heart just like a 100m sprinter......Theres just no showoff" WOW I liked what he said thats what I'am after in my life be it technology or art or just life....
KEWL
V.
Sunday, May 28, 2006
ELF CORE file optimizations in Linux, problems with non standardization of core files.
Well, all these days life is revolving on BINARY RECONSTRUCTION from the corefiles(although this is only one of the ideas I have currently for BINARY RECONSTRUCTION).
o After my deep observation of the fact why core files have some program headers which have phdr.p_filesiz==0, found that David Miller, had added some changes to the core file which the linux kernel dumps, the optimizations are ofcourse to reduce the core file size, so I guess these guys are taking off the text part of the executable and the text part of the dyanmic shared libraries.
o My Question is WHY?? WHY?? do these people just dont try to stick to standards (if some standard dont exist they should create one, and once they enhance some stuff then update the standard rather than just flushing the changes into the code), in this opensource community this is really bad that the current standard of the core file depends on few induviduals.
I checked the PHDRS (readelf --segments) the following are the PHDRS of the core.exe
o After my deep observation of the fact why core files have some program headers which have phdr.p_filesiz==0, found that David Miller, had added some changes to the core file which the linux kernel dumps, the optimizations are ofcourse to reduce the core file size, so I guess these guys are taking off the text part of the executable and the text part of the dyanmic shared libraries.
o My Question is WHY?? WHY?? do these people just dont try to stick to standards (if some standard dont exist they should create one, and once they enhance some stuff then update the standard rather than just flushing the changes into the code), in this opensource community this is really bad that the current standard of the core file depends on few induviduals.
I checked the PHDRS (readelf --segments) the following are the PHDRS of the core.exe
================================= Elf file type is EXEC (Executable file) Entry point 0x8048364 There are 11 program headers, starting at offset 52 Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align NOTE 0x000194 0x00000000 0x00000000 0x00a48 0x00000 0 **LOAD 0x001000 0x08048000 0x00000000 0x00000 0x01000 R E 0x1000 LOAD 0x001000 0x08049000 0x00000000 0x01000 0x01000 RWE 0x1000 LOAD 0x002000 0xf649b000 0x00000000 0x01000 0x01000 RWE 0x1000 **LOAD 0x003000 0xf649c000 0x00000000 0x00000 0x132000 R E 0x1000 LOAD 0x003000 0xf65ce000 0x00000000 0x03000 0x03000 RWE 0x1000 LOAD 0x006000 0xf65d1000 0x00000000 0x03000 0x03000 RWE 0x1000 LOAD 0x009000 0xf65e8000 0x00000000 0x01000 0x01000 RWE 0x1000 **LOAD 0x00a000 0xf65e9000 0x00000000 0x00000 0x15000 R E 0x1000 LOAD 0x00a000 0xf65fe000 0x00000000 0x01000 0x01000 RWE 0x1000 LOAD 0x00b000 0xfeffe000 0x00000000 0x02000 0x02000 RWE 0x1000 ====================== ============= o As I said earlier I see some of the PHDRS are having FileSiz as zero, the first (1st **ed ) PHDR which is having virtual address 0x08048000 (this is obviously) the start of the text of the program, and its not having any memory in the core file. o The other PHDRS for which FileSiz is zero correspond to the dynamic shared objects (.so) text , example in the above we see (2 **ed ) PHDR with VirtAddr as 0xf649c000 , so this means the text of some shared .so has been mapped here. o I had a question about the memory mapping with permissions r--s or r--p (gconv used by glibc gets mapped like this some time) , so does the core file contains this information of the memory mappings? IMO this content is also mapped as PROGBITS I guess not sure. o Is there a way I can findout the standard which the OS follows to write the core file? No absolutely no, solaris dumps the entire core. o Rather than depending on the OS core file, hows your opinion on writing out all the mappings form /proc/ /maps as PT_LOAD into a elf formatted file of type ET_EXEC, do you think this works? rather than converting core file to exe? Should I start working to write the standard. ======================== =============================== #include #include #include #include #include #ifndef __64_BIT__ #define __32_BIT__ #endif #ifdef __32_BIT__ #define ELF_EHDR Elf32_Ehdr #else #define ELF_EHDR Elf64_Ehdr #endif ELF_EHDR place_holder; /*Chages the elf_header in the file with ptr */ int ChangeElfHeader(int CoreFd, int WriteFd, unsigned long vaddr){ unsigned long got_len=0; if((got_len = read(CoreFd,&place_holder,sizeof(ELF_EHDR))) != sizeof(ELF_EHDR)){ perror("Unable to read the ELF Header::"); exit(1); } /*Change the ET_CORE tto ET_EXEC*/ if(place_holder.e_type == ET_CORE) { place_holder.e_type = ET_EXEC; } else { fprintf(stderr,"The file is not of ELF core file"); exit(1); } /*Change the entry */ place_holder.e_entry = vaddr; /*Write back the header*/ got_len = 0; if (( got_len = write(WriteFd,&place_holder,sizeof(ELF_EHDR))) != sizeof(ELF_EHDR)) { perror("Unable to write the header::"); exit(1); } return 1; } static void finishWriting(int coreFd, int writeFd) { unsigned char write_buffer[4*1024]; int got_len = -1; while( (got_len = read(coreFd,write_buffer,4096)) != 0) { if(write(writeFd,write_buffer,got_len) != got_len ){ perror("Unable to to write the length which was read:"); exit(1); } } close(writeFd); close(coreFd); } int main(int argc,char* argv[]){ int coreFd; int writeFd; unsigned long vaddr; if( argc < 3 ) { fprintf(stderr,"Usage core2elf core.file exe.file.name"); exit(1); } if( (coreFd = open(argv[1],O_RDONLY)) < 0) { perror("Unable to open the core file:"); exit(1); } if ((writeFd = open(argv[2],O_WRONLY| O_CREAT)) < 0) { perror("Unable to open the write file::"); exit(1); } sscanf(argv[3],"%lx",&vaddr); ChangeElfHeader(coreFd,writeFd,vaddr); finishWriting(coreFd,writeFd); } ========================= ===========================
Sunday, May 07, 2006
My F1 student visa.....
Wow its been couple of weeks of unavoidable personal work I was busy with, although I got a full support I had to do all the formalities to get enough documentation that I'am not a potential immigrant. Well it costed me my valuable time and also money (Thats OK) but not time.
The Visa officer was a nice lady she just saw my I-20 and my Transcripts and approved my visa...
Well now I'am alleviated of this pain which is unavoidable for any student who is going to U.S.
The only thing I have learned from all this excercise is JUST FINISH IT OFF, THERE IS NO WAY OUT.
VAMSI.
Saturday, March 18, 2006
Life through ELF loaders.....
Hey its a long time I have been blogging......
yes its really a tough last two weeks. From last two weeks I have been trying to get a work around to the 'exec-shield' problem we were facing. I have got a lot of new ideas on implementing this.
The following are some of the them pretty generic though
o My current problem boils down to create a executable from the running program itsself. To get this working I have been studying the kernels code in 'fs/binfmt_elf.c' especially code around 'load_elf_binary', The following are my finding might find it useful (for myself to look after some time).
-----1.)The kernels loader does not do any great , it basically gets all the metadata from the elf headers and just does the dirty work of just mapping and transferring the control. The summary of what excatly the kernel does is
a.) set the entry point from the (Elf32_Ehdr *).e_entry as the start jump to the program
b.) Load all the segments (PHDRS) the loader just deals with the program headers, it does not use any section headers. It loads all the segments with type (Elf32_Phdr *).type == PT_LOAD. If you do a 'readelf --segments a.out' you can see the segments
c.) One more important thing about how excatly it sets the 'brk' base I guess to set up the 'brk' base the kernel only (also see the copy of the email posted on linux-kernel mailing list
-----2.) Also found out that the virtual address's for the sections in the segments are the excat virtual address if they are within the range of corresponding phdr. that is I found that if .bss section has a vaddr of 0x00001000 and .data has 0x00000010 and there is a corresponding mapping (rw-p) in /proc//maps as 0x00000004-0x00010000 which includes segment to section mapping in the order '.data ...... .bss' note that .data will not start at 0x00000004 it infact still starts at 0x00000010 same with .bss. This is very logical since if the kernel's loader changes the mapping of the .data section the all the code referencing the virtual address's has to be changes. So the segments in /proc//maps file are not the segments excatly corresponding to 'readelf --segments a.out' infact they are bigger carousels with wrap around the the excat segment address's for page alignment.
More ideas next time..........
Cheers
Vamsi
o My current problem boils down to create a executable from the running program itsself. To get this working I have been studying the kernels code in 'fs/binfmt_elf.c' especially code around 'load_elf_binary', The following are my finding might find it useful (for myself to look after some time).
-----1.)The kernels loader does not do any great , it basically gets all the metadata from the elf headers and just does the dirty work of just mapping and transferring the control. The summary of what excatly the kernel does is
a.) set the entry point from the (Elf32_Ehdr *).e_entry as the start jump to the program
b.) Load all the segments (PHDRS) the loader just deals with the program headers, it does not use any section headers. It loads all the segments with type (Elf32_Phdr *).type == PT_LOAD. If you do a 'readelf --segments a.out' you can see the segments
(gdb) shell readelf --segments a.out
Elf file type is EXEC (Executable file)
Entry point 0x80482a0
There are 7 program headers, starting at offset 52
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000034 0x08048034 0x08048034 0x000e0 0x000e0 R E 0x4
INTERP 0x000114 0x08048114 0x08048114 0x00013 0x00013 R 0x1
[Requesting program interpreter: /lib/ld-linux.so.2]
LOAD 0x000000 0x08048000 0x08048000 0x004cc 0x004cc R E 0x1000
LOAD 0x0004cc 0x080494cc 0x080494cc 0x00104 0x00198 RW 0x1000
DYNAMIC 0x0004dc 0x080494dc 0x080494dc 0x000c8 0x000c8 RW 0x4
NOTE 0x000128 0x08048128 0x08048128 0x00020 0x00020 R 0x4
STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x4
Section to Segment mapping:
Segment Sections...
00
01 .interp
02 .interp .note.ABI-tag .hash .dynsym .dynstr .gnu.version .gnu.version_r .rel.dyn .rel.plt .init .plt .text .fini .rodata .eh_frame
03 .data .dynamic .ctors .dtors .jcr .got .bss
04 .dynamic
05 .note.ABI-tag
06
(gdb)
c.) One more important thing about how excatly it sets the 'brk' base I guess to set up the 'brk' base the kernel only (also see the copy of the email posted on linux-kernel mailing list
Hello All,
I have been working on an idea of creating an executable from a
running process image.
MOTIVATION:
Process migration among the nodes in distributed computing,
checkpointing process state.
BASIS:
The basis of my idea would be update the existing executable with
extra PHDRS (Program Headers) with type PT_LOAD and each of these
headers corresponding the vaddr mapping from /proc//maps.
I have done some basic study of kernels loders code in
'fs/binfmt_elf.c' especially code in 'load_elf_binary' function, the
following is my understanding.
-----------------------------
bss=0;
brk=0;
foreach (phdr in elf_header){
if(phdr->type == PT_LOAD){
if( phdr->filesize <>memsize){
/* Segment with .bss, so update brk and bss*/
}
else {
/* Just map it*/
}
}
/*Update brk bss*/
}
------------------------------------
from the above the kernel is updating brk, thus creating the start of
sbrk(0) only when it sees a PT_LOAD segment with filesize less than memsize.
The kernel will set brk base i.e sbrk(0) to the value phdr.vaddr+phdr.memsize
of the last PT_LOAD
segment its mapping? so do I need to reoder my PT_LOAD segments so
that the heap goes as the last PT_LOAD segment?
Is there any way we can tell the elf loader to force the vaddr for
sbrk(0) i.e brk base ?
Let me know your suggestion on this idea?
Really appreciate your valuable comments.
Sincerely,
Vamsi
[PS: I dont know if some one has already implemented this idea??]
-----2.) Also found out that the virtual address's for the sections in the segments are the excat virtual address if they are within the range of corresponding phdr. that is I found that if .bss section has a vaddr of 0x00001000 and .data has 0x00000010 and there is a corresponding mapping (rw-p) in /proc//maps as 0x00000004-0x00010000 which includes segment to section mapping in the order '.data ...... .bss' note that .data will not start at 0x00000004 it infact still starts at 0x00000010 same with .bss. This is very logical since if the kernel's loader changes the mapping of the .data section the all the code referencing the virtual address's has to be changes. So the segments in /proc//maps file are not the segments excatly corresponding to 'readelf --segments a.out' infact they are bigger carousels with wrap around the the excat segment address's for page alignment.
More ideas next time..........
Cheers
Vamsi
Wednesday, February 08, 2006
Presumption is a Programming Perversity..... [Discovery of new GUMPTION TRAP]
It was few weeks back in sunnyvale working on a night when I had ran out of my gumption and was almost burnt out , sitll wanted to write code to handle (In my sourcecov project) call to function pointers via 'call *%(ebp)' instruction on amd64, I ran into a problem and made a persumption on that sleepy night.......
I cannot imagine this presumption cost me 2 valuable weeks of time, which I wasted in meeting my bullshit girlfriend who has been bugging me all the way. Suddenly today after fight with her I went back (Filled with gumption) and got time to look at the code which I had left for 2 weeks with a presumption which I made that night when I saw that the debugger (gdb) itself crashed when I tried to something tricky on that sleepy night, I lost my gumption that night and presumed that its a very big problem, I was telling my self "Come on man there should be something really nasty in the code causing the debugger to crash............huh " this presumption made me very apprehensive to touch the code for two weeks :( , I have screwed the schedule with this just a crazy apprehension.
Rather than attacking the problem, I took a conventional root of comfort bought a TV to play on the XBOX with I bought it did'nt work researched on the voltage differences between india and U.S wasted my time and also wasted......Hey this reminds the the time when pheadrus took a break from answering the basic question of QUALITY, rather he went and married and forgot about QUALITY for sometime until he started thinking about it again and the mistake he made of the Presumption that QUALITY cannot be defined and took a comfort root of the question haunting him....later on he realized how big mistake it was left his wife and went on the journey of QUALITY again.
Yes even me also with this crazy prejudice lost my QUALITY track for a while.....But "Its never too late to get back..." (My Old Slang :)) ). Today I discovered a new "GUMPTION TRAP" ---> "PRESUMPTION and APPREHENSION" , probably we should have a course "GUMPTIONOLOGY101" in our school to know about all these traps rather than discovering them ourself. The problem was very silly when I got back into my QUALITY track its just that "I have been using old instructions and accessing/writing into a virtual address of the program in optimized mode when the instructions/code came from debug executable" (May be u should send me an email to explain the problem), but in a lucid manner its a very basic problem which I overlooked, its ok as long as I discover more gumption traps like this...........One thing is never presumption is bad and also evil....its a LOW QUALITY LIFE.
So today Its the 9th revision of the file just cvs commited and wanted to save my feeling to my harddisk before I forget about it......
Take care guys.....
Its always a journey no destination, you will get of QUALITY track when you say you have reached a destination
Reminds me of a quote from prisig "When you are filled with gumption there is no one stopping you from fixing the motorcycle"
Keep going guys make it a habit and enjoy it
I cannot imagine this presumption cost me 2 valuable weeks of time, which I wasted in meeting my bullshit girlfriend who has been bugging me all the way. Suddenly today after fight with her I went back (Filled with gumption) and got time to look at the code which I had left for 2 weeks with a presumption which I made that night when I saw that the debugger (gdb) itself crashed when I tried to something tricky on that sleepy night, I lost my gumption that night and presumed that its a very big problem, I was telling my self "Come on man there should be something really nasty in the code causing the debugger to crash............huh " this presumption made me very apprehensive to touch the code for two weeks :( , I have screwed the schedule with this just a crazy apprehension.
Rather than attacking the problem, I took a conventional root of comfort bought a TV to play on the XBOX with I bought it did'nt work researched on the voltage differences between india and U.S wasted my time and also wasted......Hey this reminds the the time when pheadrus took a break from answering the basic question of QUALITY, rather he went and married and forgot about QUALITY for sometime until he started thinking about it again and the mistake he made of the Presumption that QUALITY cannot be defined and took a comfort root of the question haunting him....later on he realized how big mistake it was left his wife and went on the journey of QUALITY again.
Yes even me also with this crazy prejudice lost my QUALITY track for a while.....But "Its never too late to get back..." (My Old Slang :)) ). Today I discovered a new "GUMPTION TRAP" ---> "PRESUMPTION and APPREHENSION" , probably we should have a course "GUMPTIONOLOGY101" in our school to know about all these traps rather than discovering them ourself. The problem was very silly when I got back into my QUALITY track its just that "I have been using old instructions and accessing/writing into a virtual address of the program in optimized mode when the instructions/code came from debug executable" (May be u should send me an email to explain the problem), but in a lucid manner its a very basic problem which I overlooked, its ok as long as I discover more gumption traps like this...........One thing is never presumption is bad and also evil....its a LOW QUALITY LIFE.
So today Its the 9th revision of the file just cvs commited and wanted to save my feeling to my harddisk before I forget about it......
Take care guys.....
Its always a journey no destination, you will get of QUALITY track when you say you have reached a destination
Reminds me of a quote from prisig "When you are filled with gumption there is no one stopping you from fixing the motorcycle"
Keep going guys make it a habit and enjoy it
Tuesday, November 29, 2005
Life of a hyderabadi....
"Akhir, Hyderabad ki zindagi kya he" .Whats all about hyderabadis ,and thier way of living.This mail explores certain ascpects of hyderabadi life style.I wish to seek some reviews basing on which I will post more.
A Hyderabadi on the road
It some time looks stranger than fiction when a Hyderabadi while driving on the road feels that he is the 'king of the road' and the traffic rules are meant (only )to be broken, so don't ever cross the path of a Hyderabadi when he is on the move. In case if you cross his path, he invariably tries to get into an argument as if 'raking up a fight is in the blood' of Hyderabadi.Even if he is wrong, as the proverb goes "barking dogs seldom bites "(Shara** style), he tries to get you by neck but the crowd around him stops him by holding his hands while he vainly tries to get his hand over you (a Hyderabadi seldom gets into fitscuffs )so don't worry you won't be beaten but you have to bear the choicest abuses in the
Hyderabadi slang.
The Potti Patana "Hyderabadi Ishtyle"
The bindaas attitude of Hyderabadis is personified in the numerous cafes of the city where in you get to see a whole lot of bindaas Hyderabadis sipping tea for hours together. One might wonder as to how these people have all the time in the world to indulge in such long sessions. There is so much of time available with folks over here that at times you have to literally ask them to go for want of peace.
Warning:
Beware of some nerds living around garden cafe ,Sec-Bad YMCA(Yocs and KC janta).They are extreamly intellectual and are always angry that swedish society has not awarded them nobel prizes for thier ideologies and symbolisms,trivias,Information oveload's.Make sure you drive around clock tower to avoid YMCA road , if your are a mere mortal .
"Abhi" never mean NOW...and Parson never mean day before yesterday.
eg "Parson ich apun world cup jeetenaa"
Nakko is a famous word used forever!
Lite lena mama! is ubiquitous
Irani cafe and Irani chai
A typical scene in an Irani cafe
The Steward shouts "Ye chotu ..Ek Chai La Rey" and gets it himself(!) to serve to his customers. We are talking of Irani Hotels where some people build their lives around it. They sit for hours and hours and chat with friends, families and even strangers. Irani hotels are an excellent franchise( but of course no royalty, no ownership and no rules). They can only run one way and that is successful way. Every one likes the "Chota Samosa" made out of Onions that are special to any Irani Hotel. Fine Biscuit, and the world famous Osmania biscuits were born from this concept called Irani Hotel.Some famous Iranis Cafes Blue sea, Garden,Niagra, Paradise,Madina,Sarvi.Always try to avoid cafes on lower tank bund road named as "Tea city " and "Tea Den ",For reasons follow above mentioned warning.
Gold Flake Rs 3/(rate keeps fluctuating ,includes tip for the "Khadir")- and Irani Chai along with samosa and osmania biscuit make the day for many.
Script2Executable project....
Today....I'have been thinking about this very exiting project..."SCRIPT2EXECUTABLE". I have googled on the net and found that some specific projects were existing for perl, phyton, etc.... But in this unix would we have several interpreters like expect (which I'have been using lately), lisp, csh (shell interpreters)....
So now my ideal is to create a program which takes the interpreter name and the file (script) and create a compiled executable file, which can run standalone. There are several advantages of this program one thing is that this hepls the developers to hide the code of the scripts, what are the other advantages??....
To create this generic solution, I started thinking about this idea
STEP1:
o I'll create a dummy executable file compiled, with a placeholder for the script as follows
#include
static char buffer_space_for_script[MAX_SCRIPT_FILE_SIZE]="#Cheating perl hahaha...";
/*Driver program to launch the script, similar to piping except the program reads from static buffer and writes into the pipe.*/
int main(){
int fd[2], pid;
/*create a pipe all finer details avoided*/
pipe(fd);
dup2(1,fd[1]);
pid = fork()
........
if(pid==0){
dup2(0,fd[0]);
exec(perl/other interpreter);
.....
}
else{
write(1,buffer_space_for_script,MAX_SCRIPT_SIZE); /*write into stdout will be read by interpreter in the child*/
}
Now I wanted to compile this program and use 'hexdump -c a.out" find the seek location(byte in the physical file of the buffer_space_for_script and write the contents of the script file into the file a.out)....
I almost coded it but suddently realized that the major objective of this has been breached since hexdump -c will read out the ascii, thus a intelligent user can read the script using hexdump, even though we have created a compiled executable from the script.....
:(
So now my ideal is to create a program which takes the interpreter name and the file (script) and create a compiled executable file, which can run standalone. There are several advantages of this program one thing is that this hepls the developers to hide the code of the scripts, what are the other advantages??....
To create this generic solution, I started thinking about this idea
STEP1:
o I'll create a dummy executable file compiled, with a placeholder for the script as follows
#include
static char buffer_space_for_script[MAX_SCRIPT_FILE_SIZE]="#Cheating perl hahaha...";
/*Driver program to launch the script, similar to piping except the program reads from static buffer and writes into the pipe.*/
int main(){
int fd[2], pid;
/*create a pipe all finer details avoided*/
pipe(fd);
dup2(1,fd[1]);
pid = fork()
........
if(pid==0){
dup2(0,fd[0]);
exec(perl/other interpreter);
.....
}
else{
write(1,buffer_space_for_script,MAX_SCRIPT_SIZE); /*write into stdout will be read by interpreter in the child*/
}
Now I wanted to compile this program and use 'hexdump -c a.out" find the seek location(byte in the physical file of the buffer_space_for_script and write the contents of the script file into the file a.out)....
I almost coded it but suddently realized that the major objective of this has been breached since hexdump -c will read out the ascii, thus a intelligent user can read the script using hexdump, even though we have created a compiled executable from the script.....
:(
Monday, November 07, 2005
Algorithm to build DFA's to test divisibility
I found this following algorithm very useful in designing DFA's (especially making DFA's to test the multipules, divisibility etc.....). This logic can help slove may DFA problems lets start with an example and generalize this after that..
Problem: Create a DFA to test the divisibility of a binary string by 3. (Assume the string can be scanned from left to right....ex 11 , 110 )
During the scan of the binary string the current state (Value of the binary string scanned till now) can be in one of the following states
1. 3K 2. 3K+1 3. 3K+2
So if the current state of the DFA is 3K+1 and we scan a '0' the value becomes 2*(3K+1) == 3k+2. If we scan a '1' it becomes 2*(3K+1)+1 == 3K. Similarly if we scan '0' in state '3k+2' it becomes 2*(3k+2) == 6k+4 == 3k+1. So now we have 3 states and move according to the following table.
CURRENT STATE SCAN_LITERAL NEXT_STATE
3k (final state) 1 3k+1
3k (final state) 0 3k
3k+1 1 3k
3k+1 0 3k+2
3k+2 1 3k+2
3k+2 0 3k+1
We can now extened this for the divisibility test for any 'k' that requires a D.F.A of kstates (can we minimize?). With this we can solve problems like the following.
Problem: Design a DFA for the set of string in {0,1,2}* that are ternary(base 3) representations, leading zeros permitted, of numbers that are not multiples of four.
Thought that this would be a useful piece of information.......Cheers Vamsi.
Problem: Create a DFA to test the divisibility of a binary string by 3. (Assume the string can be scanned from left to right....ex 11 , 110 )
During the scan of the binary string the current state (Value of the binary string scanned till now) can be in one of the following states
1. 3K 2. 3K+1 3. 3K+2
So if the current state of the DFA is 3K+1 and we scan a '0' the value becomes 2*(3K+1) == 3k+2. If we scan a '1' it becomes 2*(3K+1)+1 == 3K. Similarly if we scan '0' in state '3k+2' it becomes 2*(3k+2) == 6k+4 == 3k+1. So now we have 3 states and move according to the following table.
CURRENT STATE SCAN_LITERAL NEXT_STATE
3k (final state) 1 3k+1
3k (final state) 0 3k
3k+1 1 3k
3k+1 0 3k+2
3k+2 1 3k+2
3k+2 0 3k+1
We can now extened this for the divisibility test for any 'k' that requires a D.F.A of kstates (can we minimize?). With this we can solve problems like the following.
Problem: Design a DFA for the set of string in {0,1,2}* that are ternary(base 3) representations, leading zeros permitted, of numbers that are not multiples of four.
Thought that this would be a useful piece of information.......Cheers Vamsi.
Sunday, September 18, 2005
Small observation in our life
A small truth to make our Life 100% successful.......... If A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Is equal to 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Then H+A+R+D+W+O+R+K = 8+1+18+4+23+15+18+11 = 98% K+N+O+W+L+E+D+G+E = 11+14+15+23+12+5+4+7+5 = 96% L+O+V+E=12+15+22+5=54% L+U+C+K = 12+21+3+11 = 47% (None of them makes 100%) ............................... Then what makes 100% Is it Money? ..... No!!!!! Leadership? ...... NO!!!! Every problem has a solution, only if we perhaps change our "ATTITUDE". It is OUR ATTITUDE towards Life and Work that makes OUR Life 100% Successful.. A+T+T+I+T+U+D+E = 1+20+20+9+20+21+4+5 = 100
Sunday, September 11, 2005
klists an ideal way for building asynchronous applications.......
Hi doood's,
Long time blogging.....its high time now "I'am back to hack". Was following a lot of lkml threads these days to garner some intriguing suff. Just found 'KLISTS', these datastructures are highly consistent across the asynchronous processing within the kernel (basically from interrupts from the devices as well as software interrupts).
Ok let me put this in much lucid terms... 1. I have some data to be shared across process's (not threads). 2. This shared data is accessed asynchronously. We get this type of context typically in telecom applications ( I recall from my experience from moto****). They have a unix based system, with several process's running each communicating with each other.
Ok talked a lot about the problem so whats a unix way of solving it. BTW way the data should be consistent and pocess the ACID (Atomic .....dont remember :-p) behaviour i.e a typical transcational behavior, basically the solution should'nt be error prone to race conditions occuring due to asynchronous behaviour within the process's. So how do you architect this kind of applications?
Ok let me give you some really shoddy professional solution which MOTOSHIT has sold to _NEXTEL_ (being soooo dump bought it from moto***a). 1. Moto***a had a real dumb soultion, to make sure that the data is consistent across the process's they seem to use a DATABASE :)).... 2. I have seen code which tries to access a shared variable as a row in the database table. 3. They just dumbly put every shared suff in the database...to make sure that the data is having ACID properties during the modification of the data by these asynchronous process's. 4. And more ludicrously they buy a database from a shoddy database vendor informix....and just heard that they are lobbying for support form IBM for this outdated product. really amazed by the quality (the romantic quality form zen and art of motorcycle maintenance :-p) of the approach to this problem. After knowing about klists I just felt that kernel which also has asychronous stuff inside does it in a much smarter way using KLIST. (KLIST is worth a reading please use the link above).
Ok let me put this in much lucid terms... 1. I have some data to be shared across process's (not threads). 2. This shared data is accessed asynchronously. We get this type of context typically in telecom applications ( I recall from my experience from moto****). They have a unix based system, with several process's running each communicating with each other.
Ok talked a lot about the problem so whats a unix way of solving it. BTW way the data should be consistent and pocess the ACID (Atomic .....dont remember :-p) behaviour i.e a typical transcational behavior, basically the solution should'nt be error prone to race conditions occuring due to asynchronous behaviour within the process's. So how do you architect this kind of applications?
Ok let me give you some really shoddy professional solution which MOTOSHIT has sold to _NEXTEL_ (being soooo dump bought it from moto***a). 1. Moto***a had a real dumb soultion, to make sure that the data is consistent across the process's they seem to use a DATABASE :)).... 2. I have seen code which tries to access a shared variable as a row in the database table. 3. They just dumbly put every shared suff in the database...to make sure that the data is having ACID properties during the modification of the data by these asynchronous process's. 4. And more ludicrously they buy a database from a shoddy database vendor informix....and just heard that they are lobbying for support form IBM for this outdated product. really amazed by the quality (the romantic quality form zen and art of motorcycle maintenance :-p) of the approach to this problem. After knowing about klists I just felt that kernel which also has asychronous stuff inside does it in a much smarter way using KLIST. (KLIST is worth a reading please use the link above).
Monday, August 22, 2005
Solving serious problems....
I was just reading about an article about 10 best innovators in computer science. Infoworld magazine names 6 people from solaris 10 development team as best innovators. You should emphatically read the blogs of each of these sun engineers....So coming towards problems its a really hard problem to find serious and effective problems especially in computer science. Most of the research work is essentially a cliche. Frankly speaking I always do something to get a research publication, may be I feel gingerly that I dont have enough research publications compared to my friends.
Surely this kind of attitude will not help serious problems. But I have that innate feeling that I'am not doing any challenging and substantial stuff at work, so during the last few months I adopted an attitude shift in my thought "rather than complaining about the dark try to light a candle", I took all the pain to refactor every thing except the inane attitude of the superiors around, but they seem to have an attitude similar to some examples in my last post.
I quickly realised that they were just using me to their own glorification. Surely my managers are not my ideals but try to force that thought on people that they are great role models, I just keep mum. I really feel that they could really drive innovation and conceive innovative things, rather than drinking that materialistic vine.
Maan I just feel that I should do something different.
Surely this kind of attitude will not help serious problems. But I have that innate feeling that I'am not doing any challenging and substantial stuff at work, so during the last few months I adopted an attitude shift in my thought "rather than complaining about the dark try to light a candle", I took all the pain to refactor every thing except the inane attitude of the superiors around, but they seem to have an attitude similar to some examples in my last post.
I quickly realised that they were just using me to their own glorification. Surely my managers are not my ideals but try to force that thought on people that they are great role models, I just keep mum. I really feel that they could really drive innovation and conceive innovative things, rather than drinking that materialistic vine.
Maan I just feel that I should do something different.
Friday, August 19, 2005
The power of intention.
Just finished studying the book "The power of intention", really felt very inspired after reading this. Some of the authors statements had striking effect on me, statements like "Don't die with the music still left in you!!". Seemed to me a very good way to do my self talk.
Other highlights in the book which was equally striking was the authors description about the ego. The author gives the following example of how people are really blinded by this ego.
1. A tiny and thin beam of sunlight suddenly thought that is was the sun...
2. A mild ripple in the middle of the ocean suddenly beleives that its the ocean...
Yes its really true on how ego can really doom a person. If you are reading this just dont be egoistic ever in your life, just relax and think about it again.
1. A tiny and thin beam of sunlight suddenly thought that is was the sun...
2. A mild ripple in the middle of the ocean suddenly beleives that its the ocean...
Yes its really true on how ego can really doom a person. If you are reading this just dont be egoistic ever in your life, just relax and think about it again.
Thursday, July 28, 2005
Why this vacuous discernment between senior and junior?
I still remember Dr.PJN telling during my college days...."To test a person's real character, give him immense power". Its long time I'have been blogging just wanted to write about some topcoder dynamic programming problems in this post (I had drafted it may be I'll post in my next post).
All my mood is off when I see this guy walking ostentatiously all around, with a sneer unfurling those perverse insinuations, to motrify me. I guess his vanity has reached a zenith. All this is because of the discrimination the management shows between experienced and people with little experience. They just seems to despise our ideas with a prejudice that only experienced people only can make successful things and get things working, the management seems tout excessively that they will give weight to everyones views.
Its just because they think they are really privileged , they demand obligation....I really feel these are not the ideal people, no one is a junk. I'am not writing this out of jealously that they are getting paid more and are accessible to more stuff, these are words right out of a morbid mind twarthed by such inane seniors guys working along....I just learned one thing out of it although its a hard way to learn, I will never show that attitude when I become experienced. In fact I will never become a manager, its really a job with massive sagacity not to create any internal humilation among the people working under the manager.....I strongly feel that there should'nt be any discrimination among people interms of experience.
All my mood is off when I see this guy walking ostentatiously all around, with a sneer unfurling those perverse insinuations, to motrify me. I guess his vanity has reached a zenith. All this is because of the discrimination the management shows between experienced and people with little experience. They just seems to despise our ideas with a prejudice that only experienced people only can make successful things and get things working, the management seems tout excessively that they will give weight to everyones views.
Its just because they think they are really privileged , they demand obligation....I really feel these are not the ideal people, no one is a junk. I'am not writing this out of jealously that they are getting paid more and are accessible to more stuff, these are words right out of a morbid mind twarthed by such inane seniors guys working along....I just learned one thing out of it although its a hard way to learn, I will never show that attitude when I become experienced. In fact I will never become a manager, its really a job with massive sagacity not to create any internal humilation among the people working under the manager.....I strongly feel that there should'nt be any discrimination among people interms of experience.
Thursday, June 30, 2005
Verminous ego stench .........
I don't know why we(including me......) inanely always do things anticipating something, yes every one anticipates for good things to happen for their course of action. But in some cases this anticipation is different , sometimes you try to flaunt in doing things as if some one watching and you actions are mended in such a way to impress people around you. Every time you write a mail , talk to people or do some thing you want to impress people around you. But I feel that you should do things naturally but not to impress any one....the root cause of all this is ego of people . I too was a victim of it but I think I have realised some thing about it and these day I listen to people and value what they say............its ok if you are a wise man and can take great decisions but you should'nt make others feel low or jeer at people at sloppiness, but every one can slowly get things accomplished and I feel that touting may not always converge to a right solution.............and sooner or the later every one will realise this.
BTW the book I'am studying this week is "If tomorrow comes" , really a good one by sheldon makes us feel how a sapped, anguish and vindictive mind with a sedative torso feels. It was a story of a dejected lover tracy withney who tries to endure with a slender hope to seek vengeance.
TGIT (Thank God Its Thursday)
V@msi
BTW the book I'am studying this week is "If tomorrow comes" , really a good one by sheldon makes us feel how a sapped, anguish and vindictive mind with a sedative torso feels. It was a story of a dejected lover tracy withney who tries to endure with a slender hope to seek vengeance.
TGIT (Thank God Its Thursday)
V@msi
Sunday, June 26, 2005
Fervent gaming hermit....
Hmm.....finally I have moved into this reclusive world of FPS games, had spent around 90% of this weekend time quaking.....just fragged sarge 20 - 7 in a nightmare, in a map with no railguns only rocket launchers, plasma guns and shot guns (machine guns ofcourse :)) . I like this rocket launcher (although I was succumb to the rockets launched without a lot of span between walls and myself)...I almost fragged very accurately with this rocket launcher. My dodging skills are improving with every game, I felt the best way to dodge is to hold all the three keys 'w' ,'a' and 'd' which will make you move forward and press 'space' during aim and leave the keys 'a' and 'w' while shooting, this seems to be a very useful tactic of dodging, surely you can frag a human with this dodging, there are some really good players here like 'KeYmaker' and 'Devil' they fragged me couple of times. Its really great fun when you have a bunch of bacchanalian quake freaks at work places, good that I also I have 'Geforce Go' on a LCD which makes gaming more exotic.
Tuesday, June 21, 2005
Don't be afraid of making mistakes.......
Yep....I was depressed last week. But I'am starting a new life now, honestly I'am concentraring on my guitar in all my solitude they(guitar skills) seem to be improving, I feel good finally I learned to play "happy birthday......" for that special occassion next month. All this inspiration came from watching "Million dollar baby" again.......Mr.Scrape's words to danger seem to show me some light...."Any one can loose one fight....." , "Sometimes to deliver a good punch is to step back...." . And also thanks to call from karun, karun called me from canada and reminded me about st.laurel street in montreal, and about the good times we had, I really felt excited to receive his call (he will be in india soon). Sometimes this kind of suprise calls make you feel happy, and you feel something new....one more thing is I started playing cricket, people are really happy about my batting....seem's like I have'nt ever thought about my cricketing skills after a long break from club cricket during highschool...during those days I used to spend many hours to get my timing right, but was not quite getting it....but today after a long break and zero practice I'am batting like I'am in a great touch......some times when you try to work too hard on anything you don't seem to get it right (probably I'am too afraid of making mistakes during those old cricket days to get selected into the team), but when you have removed that thing of being afraid of making mistakes (because right now I dont care wether I'am in the corporate team or not) you seem to do things naturally and you get it right.......may be its a pathological example on how one should remove fear of screwing up something.........
\/ /-\ /\/\ _\"" |
Tuesday, June 07, 2005
Transmeta lessons.......
Really feel sorry about this high technology microprocessor designer. But I really appreciate their nerve to compute against titans like INTEL and AMD. I feel that monopoly is bad and it reduces innovation and checks conceiving new products. Transmeta's low-power combat against is definitely a dud, I feel that transmeta should have invested more in research to overcome the 'underpower citics' rather then demonstrating a mere obeisance, may be transmeta management failed to notice the infliction points the company has being going through, intel on the other hand have been leveraing on grove's pedagogy(Only the Paranoids survive) of identifying these infliction points and thus bashed transmeta. Intel was the first one today to get a dual-core chip out, amd followed later, but I don't why transmeta never thought about dual-cores. This indicates Intel's astute ability to pick up infliction points, but transmeta I feel should conceive something really creative to get back and start running.
I feel it as a small practical reminder about how one should always keep track of the infliction points, at any instance there are millions and millions of people competing with you and a slight negligence might create a infliction point with negative slope............ Think big to conceive a marvel.
I feel it as a small practical reminder about how one should always keep track of the infliction points, at any instance there are millions and millions of people competing with you and a slight negligence might create a infliction point with negative slope............ Think big to conceive a marvel.
Monday, May 23, 2005
Podcasting with itunes...
Ohh...that sounds 'leet right. Yes indeed it is. Thankgod no need of any external podcatchers, since every thing would be integrated in itunes itself. You just need to sync up your ipod by just connecting and you get all your favourite radio shows.
BTW the following are radiostations I'have been listening all my downtime
http://feeds.feedburner.com/ITConversations-EverythingMP3
http://www.hackermedia.net/wp-rss2.php
http://www.binrev.com/radio/podcast/
http://daily-horoscope.libsyn.com/rss/
BTW the following are radiostations I'have been listening all my downtime
http://feeds.feedburner.com/ITConversations-EverythingMP3
http://www.hackermedia.net/wp-rss2.php
http://www.binrev.com/radio/podcast/
http://daily-horoscope.libsyn.com/rss/
Sunday, May 15, 2005
Its podcasting revolution.....
Hey guys.....wondering whats new in scintillating world of gizmo's? make a guess no its not "Ipod U2" or "Ipod Shuffle"
It's not a gadget but something related to them yes its Podcasting!!. Podcasting is real fun, so what excatly is this podcasting? . hmmm..... I guess most of you have already been using RSS feeds (adding them to firefox livefeed toolbar) :-? , podcasting is akin to RSS syndication, actually normal RSS feeds get you only the text content from where ever you have subscribed the feed, now just imagine a feed which will play audio when ever you select it, rather than reading the feed you are now listening to the feed, sounds great!! right? this is excatly what is podcasting. In a little geeky terms podcasting is similar to tunnelling (protocol tunnelling) where you add (embedd) 'protocol2' in the carrier 'protocol1' as a payload, so the multimedia content is being added as the payload in RSS (Really simple syndication protocol) 2.0 protocol for syndicating audio content from the publisher.
So lets come to the bottomline "how can I get podcasting work".
1. Get a podcatcher I use doppler.
2. Configure podcatcher to integrate with mediaplayer or itunes, I use itunes and every live audio feed you add to the doppler makes it a playlist.
3. Sync up the playlist to your Ipod or any other MP3 player.
4. Enjoy podcasting (Podcasting is fun!)
You can also setup podcasting and make your blog audioblog. So get started with the pocasting revolution.....keep checking for my upcoming podcast.
Cheers!
Vamsi
Monday, May 09, 2005
Love you momma!!
Hmmm......have been thinking about too many things these days, finally I got some time to write about momma.
I just shut my mind up for few minutes and start thinking about momma feeling a little nostalgic. Momma made me realise that "success is going from failure to failure with out loss of enthusiasm", without her motivation, I would'nt have accomplished any thing till now. In fact every day is a mothers day for me.......I love you momma!!!
Wishing all of you a happy mothers day
Subscribe to:
Posts (Atom)