home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / EMXLIB8F.ZIP / EMX / LIB / GCC / ULLDIV.S < prev    next >
Encoding:
Text File  |  1993-01-02  |  3.2 KB  |  110 lines
  1. / ulldiv.s (emx+gcc) -- Copyright (c) 1992-1993 by Eberhard Mattes
  2.  
  3. / There's a better solution: set x':=x, y':=y. Shift right both x' and
  4. / y' until x' < 2^32. Then divide x' by y'. The result can be off by -1
  5. / due to the approximation. This can be checked by multiplying the
  6. / result by y and comparing to x-y. This verification step is not
  7. / required for x < 2^32.
  8. /
  9.         .globl  __ulldiv
  10.  
  11.         .text
  12.  
  13.         .align  2, 0x90
  14.  
  15. / _ulldiv_t _ulldiv (unsigned long long x, unsigned long long y)
  16.  
  17. /define saved_ebp     0(%ebp)
  18. /define ret_addr      4(%ebp)
  19. #define dst           8(%ebp)
  20. #define x_lo         12(%ebp)
  21. #define x_hi         16(%ebp)
  22. #define y_lo         20(%ebp)
  23. #define y_hi         24(%ebp)
  24.  
  25. #define quot_lo       0(%edi)
  26. #define quot_hi       4(%edi)
  27. #define rem_lo        8(%edi)
  28. #define rem_hi       12(%edi)
  29.  
  30. #define tmp_lo       %ebx
  31. #define tmp_hi       %esi
  32.  
  33. __ulldiv:
  34.         pushl   %ebp
  35.         movl    %esp, %ebp
  36.         pushl   %ebx
  37.         pushl   %esi
  38.         pushl   %edi
  39.         movl    dst, %edi
  40.         cmpl    $0, y_hi
  41.         jz      Ldiv32
  42.         movl    x_lo, %eax
  43.         movl    x_hi, %edx
  44.         movl    %eax, tmp_lo
  45.         movl    %edx, tmp_hi
  46.         xorl    %eax, %eax
  47.         xorl    %edx, %edx
  48.         movl    $64, %ecx
  49.         .align  2, 0x90
  50. 1:      shll    $1, tmp_lo                      / Shift 128 bits
  51.         rcll    $1, tmp_hi
  52.         rcll    $1, %eax
  53.         rcll    $1, %edx
  54.         subl    y_lo, %eax                      / Subtract divisor
  55.         sbbl    y_hi, %edx
  56.         jb      2f                              / Negative ->
  57.         incl    tmp_lo                          / Set bit 0 of quotient
  58.         loop    1b
  59.         jmp     3f
  60.  
  61.         .align  2, 0x90
  62. 2:      addl    y_lo, %eax                      / Restore divisor
  63.         adcl    y_hi, %edx
  64.         loop    1b
  65. 3:      movl    %eax, rem_lo
  66.         movl    %edx, rem_hi
  67.         movl    tmp_lo, quot_lo
  68.         movl    tmp_hi, quot_hi
  69. 4:      movl    %edi, %eax
  70.         popl    %edi
  71.         popl    %esi
  72.         popl    %ebx
  73.         leave
  74.         ret
  75.  
  76. /
  77. / Divide 64-bit number by 32-bit number
  78. /
  79. / 2^32 a + b         a    2^32 (a mod c) + b
  80. / ---------- = 2^32 --- + ------------------   (integer division)
  81. /      c             c           c
  82. /
  83. /
  84. / (2^32 a + b) mod c = (2^32 (a mod c) + b) mod c
  85. /
  86. / Proof:
  87.  
  88. / Divide by 2^32 c by successive subtraction (k steps) of 2^32 c.
  89. /
  90. / 2^32 a + b            2^32 a + b - 2^32 k c            2^32 (a-kc) + b
  91. / ---------- = 2^32 k + --------------------- = 2^32 k + ---------------
  92. /     c                            c                            c
  93. /
  94. / For k = [a/c], the equality 0 <= a-kc < c is true. Then, a-kc = a mod c.
  95. / For this k, the final division cannot overflow.
  96. /
  97. /
  98.         .align  2, 0x90
  99. Ldiv32:
  100.         movl    x_hi, %eax
  101.         xorl    %edx, %edx
  102.         divl    y_lo
  103.         movl    %eax, quot_hi           / high-order 32 bits of result
  104.         movl    x_lo, %eax              / remainder of prev. division in %edx
  105.         divl    y_lo
  106.         movl    %eax, quot_lo
  107.         movl    %edx, rem_lo
  108.         movl    $0, rem_hi
  109.         jmp     4b
  110.