LinuxAsmTools
Classical Puzzle 1 - Doubly linked list
We want to create a doubly linked list that can be traversed forwards or backwards. Our list must have the minimum amount of overhead. Only one dword is allowed for the headers. The function to traverse this list must work in either direction and use 6 instructions or less.
The calling sequence is:
mov edi,(current link address)
mov esi,(previous link address or zero if start of chain)
call traverse ;returns eax=next link, esi,edi unchanged
(when end of chain is encountered our function returns zero)
What code would traverse this list?
This puzzle has been solved by:
1. Gabriel Ivancescu (Bidirectional)
2.
see answer
Classical Puzzle 2 - Shared memory
Two processes are created with a shared memory area. At the top of the memory is a (dword) flag to control access. Each process must checkout the memory area by setting the flag to one before they can access it. When they are done the flag is set to zero. This is a classical problem and the flag is called a semiphore.
Intel has implemented two instructions that are suited to checking and setting the flag. It is possible to interrogate and set the flag without turning off interrupts. Write two code fragemnts using different instructions to check and set the flag. Each fragment will check the flag and if not already set, it will set the flag.
Hint: Historically this has been a very difficult problem and can get complicated. In our puzzle we assume a simple single processor application. The code fragment is less than three instructions.
This puzzle was on the web page for 6 months and not solved. The basic principles and
instructions are often discussed, but no could come up with the code? Very puzzling.
see answer
Guru Puzzle 1 - Ascii conversion
Conversion of a binary value to decimal ascii for display is a very common operation. Typically, the binary value is divided by ten and a remainder is used to form one ascii character. This algrothm produces the ascii in the wrong order and it must be reversed before sending to the display or printer. What is the shortest routine to produce a left justified decimal ascii string from the value in EAX?
The calling sequence of this function is:
mov eax,(value)
mov edi,(storage adr)
call to_ascii
(we can assume the direction flag is set to CLD state)
This puzzle was on the web page for 6 months and not solved
see answer
Guru Puzzle 2 - shortest sort
2. What is the shortest function to sort an array of dwords? The calling sequence for our function will be:
mov edi,(array address)
mov ecx,(number of elements in array)
call sort
A possible starting point is the AsmLib bubble sort program.
This puzzle was on the web page for 5 months and never solved
see answer
Bill Gates has spent the last year working on a virus to
destroy Linux. To complete his virus he needs the constant
of -4 in eax. His virus hides in the ELF header and at this
point he only has 2 bytes of program space left. All his
general registers are zero.
How does Bill generate -4 in two bytes of code?
see answer
Microsoft started taking Linux users to court with claims of stolen code.
They also entered the Linux market with thier own products. This one-two
punch has discouraged most open-source programmers and things look
bleak. You suspect their compressor uses some assembler code you wrote.
You are about to update the code and want to insert a marker that would
destroy Microsoft if they borrowed your update. Your first attempt displayed
a "(" that would not be noticed on the Microsoft compressor screen. After
some testing, you decided displaying a "1" would be better.
How would you modify the following code fragement by one byte to show a "1"?
call label
push -1014969024
label: lea ebp,[$ + 8]
call ebp
sub ebx,ebx
inc ebx
pop ecx
mov edx,ebx
mov eax,edx
inc eax
inc eax
sub ebp,byte 12
pop esi
call ebp
see answer
Answers to puzzles
Answer to Classical Puzzle 1 - Doubly linked list
There are several answers to this puzzle. A good discussion of the techniques can be found at http://en/wikipedia.org/wiki/Wike/Xor_linked_list
The answer using a Xor linked list
; input edi=current list position
; esi=previous list position or zero if at start
; output eax = next link position
; edi,esi unchanged
traverse:
xor eax,eax
or esi,esi
jz tr_10
mov eax,esi
tr_10:
xor eax,[edi]
ret
Answer to Classical Puzzle 2 - Shared Memory
semaphores on a single cpu system can often be implemented with a single xchg or cmpxchg instruction. The tricky part of this puzzle was writting the shortest code. Here is the answer:
mov ecx,1
xchg ecx,[semaphore]
jecxz got_semaphore
If the xchg returns 0 then the flag previously zero and is now one.
if the xchg returns 1 then the flag was set previously and is still set
Answer to Guru Puzzle 1 - Ascii Conversion
Conversion of a register to a decimal ascii string is easy. Just keep dividing by 10 and storing the result until the value goes negative. The tricky part is doing it in the fewest bytes of code. Our answer uses
recursion and the stack to put output in correct order.
; input
; eax=register to convert
; edi =storage pointer for ascii string
convert:
push byte 10
pop ecx
recurse:
xor edx,edx
div ecx
push edx
or eax,eax
jz store
call recurse
store:
pop eax
or al,30h
stosb
ret
The above code should compile to 22 bytes.
Answer to Guru Puzzle 2 - shortest sort
The bubble sort is the simplest sort. We just keep exchange entries if in wrong order until the list is sorted. This code works back from the end of array.
;input: ecx = number of array elements (dword array)
edi = array pointer
sort:
lea ebx,[edi+ecx*4]
mov eax,[edx]
cmploop:
lea ebx,[ebx-4]
cmp eax,[ebx]
jle notyet
xchg eax,[ebx]
notyet:
cmp ebx,edi
jnz cmploop
stosd
loop sort
ret
This should compile to 22 bytes or less
To generate -4 using using two bytes use "int byte 80h" . This calls kernel function
zero which returns error -4
To display a "1" change the instruction "sub ebx,ebx" to
"xor ebx,ebx"
Got a better Solution?
Did I type the answer in wrong?
Email solution to: jko at bsn1 dot net
or send questions, complaints, doubts, etc. to the discussion group
DesktopLinuxAsm@yahoogroups.com
join or view past messages at: yahoo
http://groups.yahoo.com/group/DesktopLinuxAsm
