1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

домыслы об int64-делении при dvs.hi <> 0

Тема в разделе "WASM.A&O", создана пользователем edemko, 19 май 2011.

  1. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    456
    мультипардон за непереведенные комментарии в блоке кода
    Код (Text):
    1. ;enu:
    2. ;thoughts on int64 division when dvs.hi <> 0
    3. ;2011_05_19, edemko@rambler.ru
    4. ;___________________________________________
    5. ;32bit machine allows division of edx:eax dividend by 32bit divisor
    6. ;we are keen on using that fact to divide unsigned int64 by int64
    7. ;
    8. ;reminder: same mul or div, applied to numerator(dividend) and denominator(divisor),
    9. ;do not change output
    10. ;indeed 200     200/100  2
    11. ;       --- =2= ------- =-= ...
    12. ;       100     100/100  1
    13. ;
    14. ;can said be used in binary?
    15. ;why not 1000b        1000b/10b  100b
    16. ;        ----- =100b= --------- =----= ...
    17. ;        0010b        0010b/10b  001b
    18. ;
    19. ;is that difficult?
    20. ;imagine small and big apple, cut each in-two - you've got 4 parts of 2 apples: 2 small and 2 big
    21. ;the pairs differ in scale only, each producing 1 on merge
    22. ;do not take numbers strict :)
    23. ;
    24. ;reminder: that's integer division cpu commonly does with DIV
    25. ;
    26. ;ok, scaling may be applied
    27. ;fake supposing: using scaling, we can reduce $ffff'ffff'ffff'ffff / $0000'0001'ffff'ffff to $ffff'ffff / $0000'0001?
    28. ;no, as the simplest proof: 99    9          100
    29. ;                           -- -> - = 9 <> ~ --- ~ 5
    30. ;                           19    1           20
    31. ;
    32. ;edx:eax = dvd & ecx:ebx = dvs
    33. ;
    34. ;reminder: after division cpu expects result to be a 32 bit value to put remainder into edx register
    35. ;there, hence, must be such dvd & dvs performation that no overflow ever occurs
    36. ;let it be dvd=$ffff'ffff'ffff'ffff and dvs made 32bit value somehow
    37. ;then dvs being $8000'0000 causes overflow: $ffff'ffff'ffff'ffff / $8000'0000 =
    38. ;                                         = $ffff'ffff'ffff'ffff / 2^31       =
    39. ;                                         = $ffff'ffff'ffff'ffff shr 31       = $0000'0001'ffff'ffff <- an odd shift somewhere required
    40. ;we should not decrease dvs any more(64->32 bits is a loss)
    41. ;relax, i was a bit lying about existence of an uprerformed dvd=$ffff'ffff'ffff'ffff and somehow performed dvs=$8000'0000
    42. ;and an odd shift somewhere required
    43. ;this is where scaling required, proportions to retain:
    44. ;initial dvd=$ffff'ffff'ffff'ffff
    45. ;initial dvs=$0000'1000'1000'0001 etc as making it 32bit, low DWord gets lost partially or totally
    46. ;bsr number_of_shifts_right,dvs gives 12 i.e. 12+1 shifts right required to make dvs 32bit value
    47. ;dvs shr 13(mind cpu supports 31 max) = $0000'0000'8000'8000
    48. ;dvd shr 13(mind cpu supports 31 max) = $0007'ffff'ffff'ffff
    49. ;
    50. ;"low DWord gets lost partially or totally"
    51. ;initial dvd=$8000'0000'0000'0000 -> shr 31 -> $0000'0001'0000'0000|lost $0000'0000 \
    52. ;initial dvs=$4000'0000'0000'0001 -> shr 31 ->           $8000'0000|lost $0000'0001 /results into 2
    53. ;reminder: compare low DWords of dvd & dvs before scaling
    54. ;in our case 0 < 1, that's why result = 2 - flags'cf = sbb 2,0 = 1
    55. ;
    56. ;how precise results of such scaling are?
    57. ;max performed dvd = $7fff'ffff'ffff'ffff ~\ 2^63 ~\
    58. ;min performed dvs = $0000'0000'8000'0000 ~/ 2^31 ~/  2^(63-31) ~ 2^32
    59. ;THAT'IS WHY LOW DWORDS MUST BE COMPARED BEFORE PERMUTATION/SCALING TO FIX FUTURE OUTPUT
    60.  
    61.  
    62.  
    63.  
    64. ;rus:
    65. ;домыслы об int64-делении при dvs.hi <> 0
    66. ;2011_05_19, edemko@rambler.ru
    67. ;___________________________________________
    68. ;32bit'ный процессор может делимое в edx:eax разделить на 32bit'ный делитель
    69. ;этого достаточно для реализации int64 на int64
    70. ;
    71. ;помни: фактор(умножение или деление), примененный к числителю(делимому) и знаменателю(делителю), конечный результат не изменит
    72. ;  200     200/100  2
    73. ;  --- =2= ------- =-= ...
    74. ;  100     100/100  1
    75. ;
    76. ;с двоичной также:
    77. ;  1000b        1000b/10b  100b
    78. ;  ----- =100b= --------- =----= ...
    79. ;  0010b        0010b/10b  001b
    80. ;
    81. ;трудно?
    82. ;оторви кусок туалетки и сложи вдвое
    83. ;возьми листок еще, сложи вдвое
    84. ;получилось 2 пары, где сумма элементов каждой = 1
    85. ;
    86. ;помни: речь идет про целочисленное деление с помощью инструкции DIV
    87. ;
    88. ;масштабировать можно, выяснили
    89. ;предположим изменив масштаб коим образом, $ffff'ffff'ffff'ffff / $0000'0001'ffff'ffff свели к $ffff'ffff / $0000'0001?
    90. ;так нельзя: 99    9          100
    91. ;            -- -> - = 9 <> ~ --- ~ 5
    92. ;            19    1           20
    93. ;
    94. ;edx:eax = dvd & ecx:ebx = dvs
    95. ;
    96. ;помни: DIV не ожидает частного более 32 бит, поскольку edx предназначен для остатка
    97. ;стоит задача изменить dvd & dvs так, что переполнение никогда не будет
    98. ;пусть dvd=$ffff'ffff'ffff'ffff и dvs как-то уместилось в 32bit
    99. ;эх, и тут переполнение:  $ffff'ffff'ffff'ffff / $8000'0000 =
    100. ;                       = $ffff'ffff'ffff'ffff / 2^31       =
    101. ;                       = $ffff'ffff'ffff'ffff shr 31       = $0000'0001'ffff'ffff <- еще 1 байт
    102. ;dvs уменшен достаточно, трогать более его не следует
    103. ;я не множко приврал про существование непропорционального dvd=$ffff'ffff'ffff'ffff и кое-как полученного dvs=$8000'0000
    104. ;никаких "еще 1 байт"
    105. ;вот где маштабирование должно быть применено правильно:
    106. ;изначально dvd=$ffff'ffff'ffff'ffff
    107. ;изначально dvs=$0000'1000'1000'0001, неважно - приводя к DWord, младшая часть может потеряться совсем
    108. ;bsr сдвигов_вправо,dvs даст 12 т.е. 12+1 сдвигов вправо для получения dvs как 32bit
    109. ;dvs shr 13(31 max - лимит цп) = $0000'0000'8000'8000
    110. ;dvd shr 13(31 max - лимит цп) = $0007'ffff'ffff'ffff
    111. ;
    112. ;"приводя к DWord, младшая часть может потеряться совсем"
    113. ;изначально dvd=$8000'0000'0000'0000 -> shr 31 -> $0000'0001'0000'0000|потеря $0000'0000 \
    114. ;изначально dvs=$4000'0000'0000'0001 -> shr 31 ->           $8000'0000|потеря $0000'0001 /2 на выходе
    115. ;помни: младшие части(DWords) dvd & dvs сравнивай перед масштабировкой
    116. ;в нашем случае 0 < 1,поэтому результат = 2-flags'cf = sbb 2,0 = 1
    117. ;
    118. ;как точны вычисления?
    119. ;max приведенный dvd = $7fff'ffff'ffff'ffff ~\ 2^63 ~\
    120. ;min приведенный dvs = $0000'0000'8000'0000 ~/ 2^31 ~/  2^(63-31) ~ 2^32
    121. ;ВРОДЕ ТОЧНО, НО... ВЫЧИСЛЕНИЯМ ДОЛЖНО ПРЕДШЕСТВОВАТЬ СРАВНЕНИЕ МЛАДШИХ ЧАСТЕЙ ЧИСЕЛ
    122.  
    123.  
    124.  
    125.  
    126. ;edx:eax <- edx:eax div ecx:ebx
    127. ;ecx:ebx <- ?
    128. ;;include once 'intro.inc'
    129. ;;intro _64div64
    130.         test    ecx,ecx
    131.         jnz     .dvs.hi_nz
    132.         test    ebx,ebx
    133.         jnz     .dvs.lo_nz
    134.         sub     edx,edx    ;stupid(how much water can be spilled through an absent chink?) rule overcome
    135.         sub     eax,eax     ;i.e. divide by zero
    136.         ret     0           ;same CTRL+SHIfT with sqrt(-etc)
    137.   .dvs.lo_nz:
    138.         mov     ecx,eax    ;keep dvd.lo
    139.         mov     eax,edx     ;to divide dvd.hi 1st
    140.         sub     edx,edx     ;
    141.         div     ebx         ;
    142.         xchg    ecx,eax    ;divide dvd.lo
    143.         div     ebx         ;
    144.         mov     edx,ecx    ;restore quo.hi
    145.         ret     0          ;hi revo!
    146.   .dvs.hi_nz:
    147.         cmp     eax,ebx    ;is dvd.lo < dvs.lo?
    148.         pushf              ;remember the answer
    149.         push    esi
    150.         mov     esi,ecx
    151.         bsr     ecx,ecx    ;so many shifts right +1 required to make dvs 32 bit size
    152.         shrd    eax,edx,cl ;compensate dvd
    153.         shr     edx,cl      ;
    154.         shrd    eax,edx,1   ;
    155.         shr     edx,1       ;
    156.         shrd    ebx,esi,cl ;as dvs is 32 bit size soon
    157.         shr     esi,cl      ;
    158.         shrd    ebx,esi,1   ;
    159.         pop     esi
    160.         div     ebx
    161.         sub     edx,edx    ;quo.hi
    162.         popf               ;so, what the answer was?
    163.         sbb     eax,edx    ;apply answer
    164.         adc     eax,edx    ;0 if 0 was initially
    165.         ret     0          ;hi amd!
    166. ;;end if
     
  2. Ezrah

    Ezrah Member

    Публикаций:
    0
    Регистрация:
    22 мар 2011
    Сообщения:
    413
    Код (Text):
    1.         title   lldiv - signed long divide routine
    2. ;***
    3. ;lldiv.asm - signed long divide routine
    4. ;
    5. ;       Copyright (c) Microsoft Corporation. All rights reserved.
    6. ;
    7. ;Purpose:
    8. ;       defines the signed long divide routine
    9. ;           __alldiv
    10. ;
    11. ;*******************************************************************************
    12.  
    13.  
    14. .xlist
    15. include cruntime.inc
    16. include mm.inc
    17. .list
    18.  
    19. ;***
    20. ;lldiv - signed long divide
    21. ;
    22. ;Purpose:
    23. ;       Does a signed long divide of the arguments.  Arguments are
    24. ;       not changed.
    25. ;
    26. ;Entry:
    27. ;       Arguments are passed on the stack:
    28. ;               1st pushed: divisor (QWORD)
    29. ;               2nd pushed: dividend (QWORD)
    30. ;
    31. ;Exit:
    32. ;       EDX:EAX contains the quotient (dividend/divisor)
    33. ;       NOTE: this routine removes the parameters from the stack.
    34. ;
    35. ;Uses:
    36. ;       ECX
    37. ;
    38. ;Exceptions:
    39. ;
    40. ;*******************************************************************************
    41.  
    42.         CODESEG
    43.  
    44. _alldiv PROC NEAR
    45.  
    46.         push    edi
    47.         push    esi
    48.         push    ebx
    49.  
    50. ; Set up the local stack and save the index registers.  When this is done
    51. ; the stack frame will look as follows (assuming that the expression a/b will
    52. ; generate a call to lldiv(a, b)):
    53. ;
    54. ;               -----------------
    55. ;               |               |
    56. ;               |---------------|
    57. ;               |               |
    58. ;               |--divisor (b)--|
    59. ;               |               |
    60. ;               |---------------|
    61. ;               |               |
    62. ;               |--dividend (a)-|
    63. ;               |               |
    64. ;               |---------------|
    65. ;               | return addr** |
    66. ;               |---------------|
    67. ;               |      EDI      |
    68. ;               |---------------|
    69. ;               |      ESI      |
    70. ;               |---------------|
    71. ;       ESP---->|      EBX      |
    72. ;               -----------------
    73. ;
    74.  
    75. DVND    equ     [esp + 16]      ; stack address of dividend (a)
    76. DVSR    equ     [esp + 24]      ; stack address of divisor (b)
    77.  
    78.  
    79. ; Determine sign of the result (edi = 0 if result is positive, non-zero
    80. ; otherwise) and make operands positive.
    81.  
    82.         xor     edi,edi         ; result sign assumed positive
    83.  
    84.         mov     eax,HIWORD(DVND) ; hi word of a
    85.         or      eax,eax         ; test to see if signed
    86.         jge     short L1        ; skip rest if a is already positive
    87.         inc     edi             ; complement result sign flag
    88.         mov     edx,LOWORD(DVND) ; lo word of a
    89.         neg     eax             ; make a positive
    90.         neg     edx
    91.         sbb     eax,0
    92.         mov     HIWORD(DVND),eax ; save positive value
    93.         mov     LOWORD(DVND),edx
    94. L1:
    95.         mov     eax,HIWORD(DVSR) ; hi word of b
    96.         or      eax,eax         ; test to see if signed
    97.         jge     short L2        ; skip rest if b is already positive
    98.         inc     edi             ; complement the result sign flag
    99.         mov     edx,LOWORD(DVSR) ; lo word of a
    100.         neg     eax             ; make b positive
    101.         neg     edx
    102.         sbb     eax,0
    103.         mov     HIWORD(DVSR),eax ; save positive value
    104.         mov     LOWORD(DVSR),edx
    105. L2:
    106.  
    107. ;
    108. ; Now do the divide.  First look to see if the divisor is less than 4194304K.
    109. ; If so, then we can use a simple algorithm with word divides, otherwise
    110. ; things get a little more complex.
    111. ;
    112. ; NOTE - eax currently contains the high order word of DVSR
    113. ;
    114.  
    115.         or      eax,eax         ; check to see if divisor < 4194304K
    116.         jnz     short L3        ; nope, gotta do this the hard way
    117.         mov     ecx,LOWORD(DVSR) ; load divisor
    118.         mov     eax,HIWORD(DVND) ; load high word of dividend
    119.         xor     edx,edx
    120.         div     ecx             ; eax <- high order bits of quotient
    121.         mov     ebx,eax         ; save high bits of quotient
    122.         mov     eax,LOWORD(DVND) ; edx:eax <- remainder:lo word of dividend
    123.         div     ecx             ; eax <- low order bits of quotient
    124.         mov     edx,ebx         ; edx:eax <- quotient
    125.         jmp     short L4        ; set sign, restore stack and return
    126.  
    127. ;
    128. ; Here we do it the hard way.  Remember, eax contains the high word of DVSR
    129. ;
    130.  
    131. L3:
    132.         mov     ebx,eax         ; ebx:ecx <- divisor
    133.         mov     ecx,LOWORD(DVSR)
    134.         mov     edx,HIWORD(DVND) ; edx:eax <- dividend
    135.         mov     eax,LOWORD(DVND)
    136. L5:
    137.         shr     ebx,1           ; shift divisor right one bit
    138.         rcr     ecx,1
    139.         shr     edx,1           ; shift dividend right one bit
    140.         rcr     eax,1
    141.         or      ebx,ebx
    142.         jnz     short L5        ; loop until divisor < 4194304K
    143.         div     ecx             ; now divide, ignore remainder
    144.         mov     esi,eax         ; save quotient
    145.  
    146. ;
    147. ; We may be off by one, so to check, we will multiply the quotient
    148. ; by the divisor and check the result against the orignal dividend
    149. ; Note that we must also check for overflow, which can occur if the
    150. ; dividend is close to 2**64 and the quotient is off by 1.
    151. ;
    152.  
    153.         mul     dword ptr HIWORD(DVSR) ; QUOT * HIWORD(DVSR)
    154.         mov     ecx,eax
    155.         mov     eax,LOWORD(DVSR)
    156.         mul     esi             ; QUOT * LOWORD(DVSR)
    157.         add     edx,ecx         ; EDX:EAX = QUOT * DVSR
    158.         jc      short L6        ; carry means Quotient is off by 1
    159.  
    160. ;
    161. ; do long compare here between original dividend and the result of the
    162. ; multiply in edx:eax.  If original is larger or equal, we are ok, otherwise
    163. ; subtract one (1) from the quotient.
    164. ;
    165.  
    166.         cmp     edx,HIWORD(DVND) ; compare hi words of result and original
    167.         ja      short L6        ; if result > original, do subtract
    168.         jb      short L7        ; if result < original, we are ok
    169.         cmp     eax,LOWORD(DVND) ; hi words are equal, compare lo words
    170.         jbe     short L7        ; if less or equal we are ok, else subtract
    171. L6:
    172.         dec     esi             ; subtract 1 from quotient
    173. L7:
    174.         xor     edx,edx         ; edx:eax <- quotient
    175.         mov     eax,esi
    176.  
    177. ;
    178. ; Just the cleanup left to do.  edx:eax contains the quotient.  Set the sign
    179. ; according to the save value, cleanup the stack, and return.
    180. ;
    181.  
    182. L4:
    183.         dec     edi             ; check to see if result is negative
    184.         jnz     short L8        ; if EDI == 0, result should be negative
    185.         neg     edx             ; otherwise, negate the result
    186.         neg     eax
    187.         sbb     edx,0
    188.  
    189. ;
    190. ; Restore the saved registers and return.
    191. ;
    192.  
    193. L8:
    194.         pop     ebx
    195.         pop     esi
    196.         pop     edi
    197.  
    198.         ret     16
    199.  
    200. _alldiv ENDP
    201.  
    202. end
     
  3. 1212

    1212 New Member

    Публикаций:
    0
    Регистрация:
    7 янв 2009
    Сообщения:
    21
    edemko!
    Если еще актуален Ваш вопрос, поясните по-русски (без приколов и жаргона) в чем проблема? Целочисленное деление в 32-х разрядной или 64-х разрядной машине?
    Если да, то какие входные условия: диапазон изменения числителя и знаменателя? если есть постоянные (особенно делитель), то какие значения они имеют? Лучше всего - постановка задачи в терминах метематики.
     
  4. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    456
    1212, прошу прощения, отписался от темы и...
    Там есть ошибка, вот новый вариант.
    Вынужденное обновление calc.
    Код (Text):
    1. ;format pe gui
    2. ;entry $
    3. ;        mov     edx,$ffff'ffff
    4. ;        mov     ecx,$ffff'ffff
    5. ;        mov     ebx,$0000'0001
    6. ;        mov     eax,$ffff'ffff
    7. ;        hlt
    8. ;        call    div64_embarcadero
    9. ;        ret
    10.  
    11.  
    12.  
    13.  
    14. ;2012/02/22, edemko@rambler.ru.
    15.  
    16.  
    17.  
    18.  
    19. ;rus: Деление 64-битных чисел без использования инструкции div
    20. ;     на 32-битном процессоре Интел 1985 года и совместимых.
    21. ;     По материалам embarcadero.
    22. ;
    23. ;     делимое             /делитель =
    24. ;     (часть1+часть2+..)  /делитель =
    25. ;     (часть1+часть2+..)*1/делитель =
    26. ;     часть1*1/делитель + часть2*1/делитель +.. =
    27. ;     часть1  /делитель + часть2  /делитель +..
    28. ;
    29. ;     Выдвинем старший бит делимого, чем не часть, разделим его на делитель - получим конкретные частное, и остаток для последующего деления.
    30. ;     Примером делимое 11110000b=240 и делитель 101b=5.
    31. ;     |11110000
    32. ;    1|1110000_ часть начинается с бита 8, частное 0|0000000, остаток 0000000|0
    33. ;   11|110000__ часть начинается с бита 7, частное 00|000000, остаток 000000|11
    34. ;  111|10000___ часть начинается с бита 6, частное 001|00000, остаток 00000|010
    35. ; -101
    36. ; =010
    37. ;  101|0000____ часть начинается с бита 5, частное 001|1|0000,остаток 00000|000
    38. ; -101
    39. ; =000
    40. ;     ... = 00110000b=48.
    41.  
    42.  
    43.  
    44.  
    45. ;enu: Int64 division avoiding div on i386 and compatible.
    46. ;     Based on embarcadero works.
    47. ;
    48. ;     dividend          /divisor =
    49. ;     (part1+part2+..)  /divisor =
    50. ;     (part1+part2+..)*1/divisor =
    51. ;     part1*1/divisor + part2*1/divisor +.. =
    52. ;     part1  /divisor + part2  /divisor +..
    53. ;
    54. ;     Pop most significant dividend bit(minimal part), divide it by divisor - get private quotient, and remainder for further division.
    55. ;     If dividend=11110000b=240 and divisor=101b=5 then
    56. ;     |11110000
    57. ;    1|1110000_ part starts at bit 8, quotient 0|0000000, ramainder 0000000|0
    58. ;   11|110000__ part starts at bit 7, quotient 00|000000, ramainder 000000|11
    59. ;  111|10000___ part starts at bit 6, quotient 001|00000, ramainder 00000|010
    60. ; -101
    61. ; =010
    62. ;  101|0000____ part starts at bit 5, quotient 001|1|0000,ramainder 00000|000
    63. ; -101
    64. ; =000
    65. ;     ... = 00110000b=48.
    66.  
    67.  
    68.  
    69.  
    70. ;edx:ecx <- edx:ecx div ebx:eax
    71. ;ebx:eax <- edx:ecx mod ebx:eax
    72. ;flags   <- ?
    73. div64_embarcadero:
    74.         test    ebx,ebx     ;dvs=0 ?
    75.         jnz     .dvs_nz
    76.         test    eax,eax
    77.         jnz     .dvs_nz
    78.         xchg    ebx,edx     ;quo=0, rem=dvd
    79.         xchg    eax,ecx
    80.         ret
    81.  
    82.   .dvs_nz:
    83.         push    ebp esi edi
    84.         mov     ebp,64      ;index
    85.         sub     esi,esi     ;part
    86.         sub     edi,edi
    87.   .loop:shl     ecx,1
    88.         rcl     edx,1
    89.         rcl     edi,1
    90.         rcl     esi,1
    91.         cmp     esi,ebx     ;part ?
    92.         jb      .no_part
    93.         ja      .part
    94.         cmp     edi,eax
    95.         jb      .no_part
    96.   .part:sub     edi,eax
    97.         sbb     esi,ebx
    98.         inc     ecx         ;quo
    99.   .no_part:
    100.         dec     ebp
    101.         jnz     .loop
    102.         mov     ebx,esi     ;rem
    103.         mov     eax,edi
    104.         pop     edi esi ebp
    105.         ret