QualityCentral

Public Report

Report From: Delphi-BCB/RTL/Delphi/Arithmetic [ Add a report in this area ]

Report #: 34053

Status: Open

Improved 64 bit modulus function (__llmod)

Project: Delphi

Build #: 10.0

Version: 10.0

Submitted By: John O'Harrow

Report Type: Suggestion / Enhancement Request

Date Reported: 9/17/2006 7:25:07 AM

Severity: Infrequently encountered problem

Last Updated: 3/20/2012 2:24:39 AM

Platform: All versions

Internal Tracking #: 242409

Resolution: None (Resolution Comments)

Resolved in Build: : None

Duplicate of: None

Voting and Rating

Overall Rating: (7 Total Ratings)

4.57 out of 5

Total Votes: 10

Description

The __llmod function in systemm.pas can easily be improved by replacing it with the functio nlisted in "Workaround"

Steps to Reproduce:

None

Workarounds

(* ***** BEGIN LICENSE BLOCK *****
* Version: MPL 1.1
*
* The implementation of function __llmod is subject to the
* Mozilla Public License Version 1.1 (the "License"); you may
* not use this file except in compliance with the License.
* You may obtain a copy of the License at http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
* for the specific language governing rights and limitations under the
* License.
*
* Portions created by the Initial Developer are Copyright (C) 2002-2004
* the Initial Developer. All Rights Reserved.
*
* Contributor(s): John O'Harrow
*
* ***** END LICENSE BLOCK ***** *)

// ----------------------------------------------------------------------------
//  64-bit modulo
// ----------------------------------------------------------------------------

//  Dividend(EDX:EAX), Divisor([ESP+8]:[ESP+4])

procedure __llmod;
asm
  push    ebx                {save used registers}
  push    esi
  push    edi
  mov     ebx, [esp+16]      {divisor-lo}
  mov     ecx, [esp+20]      {divisor-hi}
  mov     esi, edx
  sar     esi, 31            {0 if Dividend < 0 else -1}
  mov     edi, edx
  sar     edi, 31
  xor     eax, edi
  xor     edx, edi
  sub     eax, edi
  sbb     edx, edi           {edx:eax = abs(Dividend)}
  mov     edi, ecx
  sar     edi, 31
  xor     ebx, edi
  xor     ecx, edi
  sub     ebx, edi
  sbb     ecx, edi           {ecx:ebx = abs(Divisor)}
  jnz     @@BigDivisor       {jump if divisor >= 2^32}
  cmp     edx, ebx           {dividend-hi < divisor-hi?}
  jb      @@OneDiv           {yes, only one division needed}
  mov     ecx, eax           {ecx = dividend-lo}
  mov     eax, edx           {eax = dividend-hi}
  xor     edx, edx           {zero extend it into edx:eax}
  div     ebx                {eax = quotient-hi}
  mov     eax, ecx           {eax = dividend-lo}
@@OneDiv:
  div     ebx
  mov     eax, edx           {eax = quotient-lo}
  xor     edx, edx           {edx = quotient-hi = 0}
  jmp     @@SetSign          {remainder in edx:eax}
@@BigDivisor:
  cmp     edx, ecx           {dividend-hi < divisor-hi?}
  jb      @@SetSign          {yes, result = dividend}
@@BigDiv:
  push    edx                {save dividend-hi}
  push    eax                {save dividend-lo}
  push    ebx                {save divisor-lo}
  mov     edi, ecx           {with divisor (ecx:ebx) and dividend (edx:eax)}
  shr     edx, 1             { shift both}
  rcr     eax, 1             {  dividend and}
  ror     edi, 1             {   divisor}
  rcr     ebx, 1             {    right by 1 bit}
  bsr     ecx, ecx           {get number of remaining shifts}
  shrd    ebx, edi, cl       {scale down divisor and}
  shrd    eax, edx, cl       {  dividend such that divisor}
  shr     edx, cl            {    is less than 2^32}
  rol     edi, 1             {restore original divisor-hi}
  div     ebx                {compute quotient}
  mov     ecx, eax           {save quotient}
  imul    edi, eax           {quotient * divisor-hi}
  pop     ebx                {divisor-lo}
  mul     ebx                {quotient * divisor-lo}
  pop     ebx                {dividend-lo}
  add     edx, edi           {edx:eax = quotient * divisor}
  sub     ebx, eax           {dividend-lo - (quotient*divisor-lo)}
  mov     eax, ecx           {get quotient}
  pop     ecx                {dividend-hi}
  sbb     ecx, edx           {divisor * quotient from dividend}
  sbb     eax, eax           {if remainder < 0 then -1 else 0}
  mov     edx, [esp+20]      {divisor-hi}
  and     edx, eax           {if remainder < 0 then divisor-hi else 0}
  and     eax, [esp+16]      {if remainder < 0 then divisor-lo else 0}
  add     eax, ebx           {remainder-lo}
  add     edx, ecx           {remainder-hi}
@@SetSign:
  xor     eax, esi           {if (remainder < 0)}
  xor     edx, esi           {  compute 1's complement of result}
  sub     eax, esi           {if (remainder < 0)}
  sbb     edx, esi           {  compute 2's complement of result}
  pop     edi                {restore used registers}
  pop     esi
  pop     ebx
  ret     8
end;

Attachment

None

Comments

John O'Harrow at 9/21/2006 2:43:56 AM -

My proposed replacement it typically 80% faster than the existing RTL version

Developer Tools

Database Tools