Working on some condition-control block
I ran to a small problem that might be interesting
from academic "size-optimization" point of view
for fun.
Problem:


We have eax = [0..5]
and to closely placed vars:
cond_0 db
cond_1 db
if eax < 3
cond_0 <- al
else (eax >=3)
cond_1 <- (al-3)

other regs - undefind
so problem summary is
1) to reflect value in al this way:
0->0
1->1
2->2
3->0
4->1
5->2
2)if eax was >=3 then shift pointer by one
(in wich direction depends on what offset you placed for initial
pointer)

Task is create
1. Smallest unbranchable code
2. Smallest branchable code

After first akward ideas like
branch:


mov edi,offset cond_1
sub eax,3
jnc @F
dec edi
add eax,3
@@:
stosb

unbranch:


mov edi,offset cond_0
sub eax,3
sbb edx,edx
sub edi,edx
and edx,3
add eax,edx
stosb


It's occured to me that al/3 has reminder needed for value to place
and quontient as value to correct pointer.
The thing is to find a way to use fact of quontient value
for correction the shortest way (if there is one) is escaping
my mind, might be you can find a shorter way ;)
Or even find complitly different algorithm shorter than this one.
For now I have:

branche:


mov edi,offset cond_0
db 0D4h, 03
test ah,ah
jt @F
inc edi
stosb


unbranche ver.1:


mov edi,offset cond_1
db 0D4h,03
sub ah,1 ;or cmp ah,1
sbb edi,0
stosb


unbranche ver.2:


mov edi,offset cond_1
cmp eax,3
sbb edi,0
db 0D4h,03
stosb


Any ideas to shorten it?
Posted on 2004-08-06 06:35:10 by The Svin
First thought:
 cmp eax,3

sbb edi,edi
db 0D4h,03
add edi,offset cond_1
stosb
...no really bright ideas, yet.

What about the flags set by AAM?
Posted on 2004-08-06 08:26:17 by bitRAKE
I dont have all my assembly references with me here, and this might or might
not be the correct syntax (or any faster), but I thought a jump table might help...

Something close to:


.DATA
JmpTbl DD ADDR cond_0, ADDR cond_0, ADDR cond_0
DD ADDR cond_1, ADDR cond_1, ADDR cond_1

cond_0 DB ?
cond_1 DB ?

.CODE
mov EDX, EAX
lea ECX, [JmpTbl]
and EDX, 03h
mov [ECX+EAX], BYTE PTR EDX
Posted on 2004-08-06 08:57:43 by Graebel

First thought:

Good one!

Graebel,
your code is much longer :)
Posted on 2004-08-06 09:58:14 by The Svin
AAM seems to be the most efficient way to get remainder, in terms of size. I thought about maybe adding one to EAX if greaterthan two, then adjusting EDI based on bit-2:

cmp eax, 3
cmc
adc eax, 0
btr eax, 2
adc edi, 0
stosb

...but I haven't thought of a way to reduce code size.


cmp eax, 3
sbb edi, edi
cmc
adc eax, 0
btr eax, 2
add edi, offset cond_1
stosb

...really no help. :stupid:
Posted on 2004-08-06 10:00:54 by bitRAKE
I was confused a little bit what is h_Window,
I think, the code should be like


..
cond_0 db
cond_1 db
...
cmp eax,3
sbb edi,edi
db 0D4h,03
add edi,offset cond_1 ;edi = offset cond_1 if eax >3;
;else edi=(offset cond_1) -1
stosb


pointer handling size is the same size as in


mov edi,offset ..
cmp eax,3

adc edi,0 (or sbb edi,0)
...



(5+3 (mov reg,imm + adc reg,imm8) vs. 6+2 (sbb reg,imm8 + add reg,imm32)
Yet it's another way to do the job that's what I like about it.
Posted on 2004-08-06 10:16:57 by The Svin
Drat, well it was worth a shot. Without my references im blind... :cool:

Its about time I corrected that.
I think im going to install some things over lunch time today.
Posted on 2004-08-06 10:37:00 by Graebel

Drat, well it was worth a shot

Of course it was. It always does.
PS.
A little bit knowlige about opcode format structure, could help if you don't have refferences.
Usually when you know it, most of the time you know size without debugger or refference.
Posted on 2004-08-06 14:34:11 by The Svin
The following two are both 11 bytes in size:
push 3

pop ecx
idiv ecx
mov [cond_0+eax],dl

db 0d4h,3

movzx ecx,ah
mov [cond_0+ecx],al
Posted on 2004-08-06 19:13:27 by Sephiroth3
Sephiroth3, you are continually impressive! :cool:
Posted on 2004-08-06 20:28:22 by bitRAKE
Sephiroth3
That is it! Though it was obvious that quotient can be used as displacement I've trapped myself with prejustive conclusion that moving intial pointer to edi with consequent stosb would be the shortest way :)
I should have forgotten about "edi-stosb" for a while to consider different ways using quontien as displacement.
Thank you. That is exactly what I called "escaping my mind"
Posted on 2004-08-07 06:49:04 by The Svin