Help:Divide overflow error

From: ppw (ppw_at_pobox.net)
Date: 02/13/04 

Date: Fri, 13 Feb 2004 19:00:48 +0000 (UTC)

Hello. I would like to ask people if they could
help me with one algorithm, which seems OK to me,
but after the first IDIV instruction my program
from which the procedure (the algorithm) was called crashes to operating
system with 'Divide overflow' error message. If you could help me, I would
be really grateful. Thank you.

The point is:
My procedure ('powermod') performs this mathematic operation:

Y = X^S mod R

(X < R) for known X, S and R which are words (16bit).
>>From this is clear that we need to work with 32bit registers (e??).

Common arithmetic solution would be VERY slow and thus I know a better
way to solve this problem. The algorithm that does this is:

 1) first, we will define S as a binary number:
    S = s_0 + 2*s_1 + 4*s_2 + ... + 2^{k-1}*s_{k-1}
    (we can say that S has k bits, in our case k = 16)
 2) if s_0 = 1, then A := X, else A = 1
 3) let Y_1 := X^2 mod R
    (respectively Y_1 := Y_0^2 mod R, where Y_0 := X)
 4) if s_1 = 1, then A := A*Y_1 mod R, else do not modify A
 5) let Y_2 := Y_1^2 mod R
 6) if s_2 = 1, then A := A*Y_2 mod R, else do not modify A
 ...
 7) repeat steps 5) and 6) for Y_3 and s_3, Y_4 and s_4, ... , until
    we reach Y_{k-1} and s_{k-1}
 8) after k steps, A holds the result

My algorithm is below. PLEASE
suggest another solution. I would
REALLY appreciate it. Anyway, thanks for reading till now ;)

One more comment:
SI register holds offset to a bit mask (to get s_0, s_1, ... , s_15
values), where the bit masks are defined in data segment this way:

BitMasks dw 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768

(1 = 0000000000000001b,
 2 = 0000000000000010b,
 4 = 0000000000000100b,
 ...
 32768 = 1000000000000000b)

Thank you.

"XM"

OK, here's the code:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; calculates equation: Y = X^S mod R (X < R)
; bx = X value
; cx = S value
; dx = R value
; regs destroyed: eax, ebx, cx, edx, si, edi
; return values: ax = Y value

powermod proc near

  ; set up ebx from bx

  ; mov di, bx ; this is the slow way
  ; xor ebx, ebx
  ; movzx ebx, di
  movzx ebx, bx ; fast way

  ; set up edx from dx

  ; mov di, dx ; this is the slow way
  ; xor edx, edx
  ; movzx edx, di
  movzx edx, dx ; fast way

  ; bit mask offset, initial is zero
  xor si, si

  ; A value setup

  ; get s_0 value
  mov di, cx
  and di, BitMasks+2[si]

  ; autoincrement bit mask index
  add si, 2

  ; is s_0 = 1?
  or di, di

  ; if yes, go to nozero0
  jnz notzero0

  ; s_0 = 0, so A = 1
  ; we will use EAX to hold A value
  mov eax, 1
  jmp begineqninit

notzero0:

  ; s_0 = 1, so A = X
  mov eax, ebx

begineqninit:

  ; Y_0 setup
  ; we will use EDI to store Y_? values
  ; at the beginning EDI == Y_0 := X
  mov edi, ebx

  ; follows the calculation loop

begineqn:

  ; Y_0^2 mod R ( = Y_1 ) follows
  ; (EDI^2 mod R respectively)

  push eax
  push ebx

  mov eax, edi
  mov ebx, edi
  imul ebx

  ; save EDI^2 into EDI
  ; we will assume EDI is < 2^16 so EDI^2 will also fit into 32bit register
  ; comment: this is true since X is a word (16bit number)
  ; (so EDX -- upper 32 bits -- will be zeroes)
  mov edi, eax

  pop ebx
  pop eax

  ; now EDI = Y_0^2, follows EDI mod R

  push eax
  push ebx
  push edx

  ; EBX holds the divider (R)
  mov ebx, edx

  ; EDX:EAX is the dividend (upper and lower 32bits)
  ; EDX is null, EAX = EDI
  xor edx, edx
  mov eax, edi

  ; comment:
  ; *** AT THIS POINT 'Divide overflow' IS GENERATED
  ; *** DON'T KNOW WHY...
  idiv ebx

  ; EDX holds remainder - EDI mod R
  ; we will save this into EDI, now EDI := Y_0^2 mod R
  mov edi, edx

  pop edx
  pop ebx
  pop eax

  ; now EDI := Y_0^2 mod R == Y_1
  push edi

  ; check for s_1 (s_2, ... , s_15)
  mov di, cx
  and di, BitMasks+2[si]
  add si, 2

  or di, di
  jnz notzero1

  pop edi
  jmp powercont

notzero1:

  ; follows A := A*Y_1 mod R
  ; EAX = A, EDI = Y_1
  pop edi

  ; A := A*Y_1
  imul edi
  
  ; now EAX = A*Y_1, follows EAX mod R

  push ebx
  push edx

  mov ebx, edx ; EBX is the divider (R)
  xor edx, edx ; EDX is zero (upper 32bits of dividend)
               ; EAX is set (A)

  idiv ebx

  ; EDX holds remainder - EAX mod R
  ; we will save this value into EAX (A)
  mov eax, edx

  pop edx
  pop ebx

  ; now EAX == A := A*Y_1 mod R

powercont:

  ; are we at the end?
  ; when SI = 32 then we are, since after 16 steps SI = 16*2 = 32
  cmp si, 32
  jnz begineqn

  ; and now EAX (respectively AX) holds the result (X^S mod R)

  ret
powermod endp

Relevant Pages