Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Solved

Posted on 2003-11-03

hello experts~!

i have a homework and i'm a bit stuck on it... i would appriciate if you could give me a jump start (pseudo code or c/c++ is fine).

assembler: NASM

problem: take a decimal interger (from register) and convert it into ascii characters (in a array)

basicly: int i = 123;

result char j[]= {'1', '2', '3'};

regards,

kosmoludek

i have a homework and i'm a bit stuck on it... i would appriciate if you could give me a jump start (pseudo code or c/c++ is fine).

assembler: NASM

problem: take a decimal interger (from register) and convert it into ascii characters (in a array)

basicly: int i = 123;

result char j[]= {'1', '2', '3'};

regards,

kosmoludek

4 Comments

char *itoa(char buffer[12], int i)

{

char *back;

back = buffer + 11;

*back = 0;

do {

*--back = i % 10 + '0';

i /= 10;

} while (i);

return back;

}

In assembly, the IDIV instruction computes both quotient and remainder. You can also avoid using division entirely, but that's more difficult.

how can you divide without using division ?

I'm not looking for the full code or anything, but just an idea of where you were going.

My guess though there is another way, where you just don't use division, so it's not "divide without division", but rather something else.

Copied from pentopt.pdf (a one stop resource for assembly optimization)

Dividing by a constant can be done by multiplying with the reciprocal. A useful algorithm for

integer division by a constant is as follows:

To calculate the unsigned integer division q = x / d, you first calculate the reciprocal of the

divisor, f = 2r / d, where r defines the position of the binary decimal point (radix point). Then

multiply x with f and shift right r positions. The maximum value of r is 32+b, where b is the

number of binary digits in d minus 1. (b is the highest integer for which 2b ? d). Use r = 32+b

to cover the maximum range for the value of the dividend x.

This method needs some refinement in order to compensate for rounding errors. The

following algorithm will give you the correct result for unsigned integer division with

truncation, i.e. the same result as the DIV instruction gives (Thanks to Terje Mathisen who

invented this method):

b = (the number of significant bits in d) - 1

r = 32 + b

f = 2r / d

If f is an integer then d is a power of 2: goto case A.

If f is not an integer, then check if the fractional part of f is < 0.5

If the fractional part of f < 0.5: goto case B.

If the fractional part of f > 0.5: goto case C.

case A (d = 2b):

result = x SHR b

case B (fractional part of f < 0.5):

round f down to nearest integer

result = ((x+1) * f) SHR r

case C (fractional part of f > 0.5):

round f up to nearest integer

result = (x * f) SHR r

Example:

Assume that you want to divide by 5.

5 = 101B.

b = (number of significant binary digits) - 1 = 2

r = 32+2 = 34

f = 234 / 5 = 3435973836.8 = 0CCCCCCCC.CCC...(hexadecim

The fractional part is greater than a half: use case C.

Round f up to 0CCCCCCCDH.

The following code divides EAX by 5 and returns the result in EDX:

MOV EDX, 0CCCCCCCDh

MUL EDX

SHR EDX,2

After the multiplication, EDX contains the product shifted right 32 places. Since r = 34 you

have to shift 2 more places to get the result. To divide by 10, just change the last line to SHR

EDX,3.

In case B we would have:

ADD EAX, 1

MOV EDX, f

MUL EDX

SHR EDX, b

This code works for all values of x except 0FFFFFFFFH which gives zero because of

overflow in the ADD EAX,1 instruction. If x = 0FFFFFFFFH is possible, then change the

code to:

MOV EDX,f

ADD EAX,1

JC DOVERFL

MUL EDX

DOVERFL: SHR EDX,b

I

f the value of x is limited, then you may use a lower value of r, i.e. fewer digits. There can

be several reasons for using a lower value of r:

? you may set r = 32 to avoid the SHR EDX,b in the end.

? you may set r = 16+b and use a multiplication instruction that gives a 32-bit result

rather than 64 bits. This will free the EDX register:

IMUL EAX,0CCCDh / SHR EAX,18

? you may choose a value of r that gives case C rather than case B in order to avoid

the ADD EAX,1 instruction

The maximum value for x in these cases is at least 2r-b, sometimes higher. You have to do

a systematic test if you want to know the exact maximum value of x for which the code

works correctly.

You may want to replace the slow multiplication instruction with faster instructions as

explained on page 114.

The following example divides EAX by 10 and returns the result in EAX. I have chosen r=17

rather than 19 because it happens to give a code that is easier to optimize, and covers the

same range for x. f = 217 / 10 = 3333h, case B: q = (x+1)*3333h:

LEA EBX,[EAX+2*EAX+3]

LEA ECX,[EAX+2*EAX+3]

SHL EBX,4

MOV EAX,ECX

SHL ECX,8

ADD EAX,EBX

SHL EBX,8

ADD EAX,ECX

ADD EAX,EBX

SHR EAX,17

A systematic test shows that this code works correctly for all x < 10004H.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Title | # Comments | Views | Activity |
---|---|---|---|

Net framework versions 2.0 and sdk | 4 | 512 | |

Help with Assembly Language Program | 2 | 1,308 | |

Request a tutorial for MS Assembly | 3 | 318 | |

recovering cyptowalled files | 2 | 963 |

Join the community of 500,000 technology professionals and ask your questions.