configurable fixed-bit-size signed big integer implementation

biginttest.dpr

program biginttest;
{$ifdef fpc}
 {$mode delphi}
{$endif}
{$APPTYPE CONSOLE}

(******************************************************************************
 *                                zlib license                                *
 *============================================================================*
 *                                                                            *
 * Copyright (c) 2015, Benjamin Rosseaux (benjamin@rosseaux.de)               *
 *                                                                            *
 * This software is provided 'as-is', without any express or implied          *
 * warranty. In no event will the authors be held liable for any damages      *
 * arising from the use of this software.                                     *
 *                                                                            *
 * Permission is granted to anyone to use this software for any purpose,      *
 * including commercial applications, and to alter it and redistribute it     *
 * freely, subject to the following restrictions:                             *
 *                                                                            *
 * 1. The origin of this software must not be misrepresented; you must not    *
 *    claim that you wrote the original software. If you use this software    *
 *    in a product, an acknowledgement in the product documentation would be  *
 *    appreciated but is not required.                                        *
 * 2. Altered source versions must be plainly marked as such, and must not be *
 *    misrepresented as being the original software.                          *
 * 3. This notice may not be removed or altered from any source distribution. *
 *                                                                            *
 ******************************************************************************)

{$ifdef fpc}
 {$undef OldDelphi}
{$else}
 {$ifdef conditionalexpressions}
  {$if CompilerVersion>=23.0}
   {$undef OldDelphi}
type qword=uint64;
     ptruint=NativeUInt;
     ptrint=NativeInt;
  {$else}
   {$define OldDelphi}
  {$ifend}
 {$else}
  {$define OldDelphi}
 {$endif}
{$endif}
{$ifdef OldDelphi}
type qword=int64;
{$ifdef cpu64}
     ptruint=qword;
     ptrint=int64;
{$else}
     ptruint=longword;
     ptrint=longint;
{$endif}
{$endif}

const IntegerValueBits=2048; // must be divisible by 32, because a limb in this implementation is a 32-bit dword
      IntegerValueDWords=IntegerValueBits shr 5;

type PIntegerValue=^TIntegerValue;
     TIntegerValue=array[0..IntegerValueDWords-1] of longword;

procedure IntegerValueSetInt64(out Dest:TIntegerValue;const Value:int64);
var LimbIndex:longint;
    SignValue:longword;
begin
 Dest[0]:=qword(Value) and $ffffffff;
 Dest[1]:=qword(Value) shr 32;
 SignValue:=-(qword(Value) shr 63);
 for LimbIndex:=2 to IntegerValueDWords-1 do begin
  Dest[LimbIndex]:=SignValue;
 end;
end;

procedure IntegerValueSetQWord(out Dest:TIntegerValue;const Value:qword);
var LimbIndex:longint;
begin
 Dest[0]:=qword(Value) and $ffffffff;
 Dest[1]:=qword(Value) shr 32;
 for LimbIndex:=2 to IntegerValueDWords-1 do begin
  Dest[LimbIndex]:=0;
 end;
end;

function IntegerValueGetInt64(const Source:TIntegerValue):int64;
begin
 result:=Source[0] or (int64(Source[1]) shl 32);
end;

function IntegerValueGetQWord(const Source:TIntegerValue):qword;
begin
 result:=Source[0] or (qword(Source[1]) shl 32);
end;

procedure IntegerValueAdd(out Dest:TIntegerValue;const a,b:TIntegerValue);
var LimbIndex:longint;
    Carry:longword;
    Value:qword;
begin
 Carry:=0;
 for LimbIndex:=0 to IntegerValueDWords-1 do begin
  Value:=qword(a[LimbIndex])+qword(b[LimbIndex])+qword(Carry);
  Carry:=Value shr 32;
  Dest[LimbIndex]:=Value and $ffffffff;
 end;
end;

procedure IntegerValueSub(out Dest:TIntegerValue;const a,b:TIntegerValue);
var LimbIndex:longint;
    Borrow:longword;
    Value:qword;
begin
 Borrow:=0;
 for LimbIndex:=0 to IntegerValueDWords-1 do begin
  Value:=(qword(a[LimbIndex])-qword(b[LimbIndex]))-Borrow;
  Borrow:=Value shr 63;
  Dest[LimbIndex]:=Value and $ffffffff;
 end;
end;

function IntegerValueIsZero(const Source:TIntegerValue):boolean;
var LimbIndex:longint;
begin
 result:=true;
 for LimbIndex:=0 to IntegerValueDWords-1 do begin
  if Source[LimbIndex]<>0 then begin
   result:=false;
   exit;
  end;
 end;
end;

function IntegerValueIsOne(const Source:TIntegerValue):boolean;
var LimbIndex:longint;
begin
 result:=Source[0]=1;
 if result then begin
  for LimbIndex:=1 to IntegerValueDWords-1 do begin
   if Source[LimbIndex]<>0 then begin
    result:=false;
    exit;
   end;
  end;
 end;
end;

function IntegerValueIs32Bit(const Source:TIntegerValue):boolean;
var LimbIndex:longint;
begin
 result:=true;
 if (Source[IntegerValueDWords-1] and longword($80000000))<>0 then begin
  for LimbIndex:=1 to IntegerValueDWords-1 do begin
   if Source[LimbIndex]<>longword($ffffffff) then begin
    result:=false;
    exit;
   end;
  end;
 end else begin
  for LimbIndex:=1 to IntegerValueDWords-1 do begin
   if Source[LimbIndex]<>0 then begin
    result:=false;
    exit;
   end;
  end;
 end;
end;

function IntegerValueIsXBit(const Source:TIntegerValue;const Bits:longint):boolean;
var LimbIndex:longint;
begin
 if (Source[IntegerValueDWords-1] and longword($80000000))<>0 then begin
  if (Bits and 31)<>0 then begin
   result:=(Source[(Bits and not 32) shr 5] shr (Bits and 31))=(longword($ffffffff) shr (Bits and 31));
  end else begin
   result:=true;
  end;
  if result then begin
   for LimbIndex:=((Bits+31) and not 32) shr 5 to IntegerValueDWords-1 do begin
    if Source[LimbIndex]<>$ffffffff then begin
     result:=false;
     exit;
    end;
   end;
  end;
 end else begin
  if (Bits and 31)<>0 then begin
   result:=(Source[(Bits and not 32) shr 5] shr (Bits and 31))=0;
  end else begin
   result:=true;
  end;
  if result then begin
   for LimbIndex:=((Bits+31) and not 32) shr 5 to IntegerValueDWords-1 do begin
    if Source[LimbIndex]<>0 then begin
     result:=false;
     exit;
    end;
   end;
  end;
 end;
end;

function IntegerValueNegative(const Source:TIntegerValue):boolean;
begin
 result:=(Source[IntegerValueDWords-1] and longword($80000000))<>0;
end;

function IntegerValueEquals(const a,b:TIntegerValue):boolean;
var LimbIndex:longint;
begin
 result:=true;
 for LimbIndex:=0 to IntegerValueDWords-1 do begin
  if a[LimbIndex]<>b[LimbIndex] then begin
   result:=false;
   exit;
  end;
 end;
end;

function IntegerValueCompare(const a,b:TIntegerValue):longint;
var LimbIndex:longint;
    NegativeA,NegativeB:boolean;
begin
 NegativeA:=(a[IntegerValueDWords-1] and longword($80000000))<>0;
 NegativeB:=(b[IntegerValueDWords-1] and longword($80000000))<>0;
 if NegativeA=NegativeB then begin
  // Both positive or negative
  for LimbIndex:=IntegerValueDWords-1 downto 0 do begin
   if a[LimbIndex]<>b[LimbIndex] then begin
    if a[LimbIndex]>b[LimbIndex] then begin
     result:=1;
    end else if a[LimbIndex]<b[LimbIndex] then begin
     result:=-1;
    end;
    exit;
   end;
  end;
  result:=0;
 end else if NegativeA then begin
  // negative a < positive b
  result:=-1;
 end else{if NegativeB then}begin
  // positive a > negative b
  result:=1;
 end;
end;

function IntegerValueUnsignedCompare(const a,b:TIntegerValue):longint;
var LimbIndex:longint;
begin
 result:=0;
 for LimbIndex:=IntegerValueDWords-1 downto 0 do begin
  if a[LimbIndex]<>b[LimbIndex] then begin
   if a[LimbIndex]>b[LimbIndex] then begin
    result:=1;
   end else if a[LimbIndex]<b[LimbIndex] then begin
    result:=-1;
   end;
   exit;
  end;
 end;
end;

procedure IntegerValueNEG(out Dest:TIntegerValue;const Source:TIntegerValue);
var Index:longint;
    Carry:longword;
    Value:qword;
begin
 Carry:=1;
 for Index:=0 to IntegerValueDWords-1 do begin
  Value:=qword(longword(not Source[Index]))+qword(Carry);
  Carry:=Value shr 32;
  Dest[Index]:=Value and $ffffffff;
 end;
end;

procedure IntegerValueABS(out Dest:TIntegerValue;const Source:TIntegerValue);
var Index:longint;
    Carry:longword;
    Value:qword;
begin
 if (Source[IntegerValueDWords-1] and longword($80000000))<>0 then begin
  Carry:=1;
  for Index:=0 to IntegerValueDWords-1 do begin
   Value:=qword(longword(not Source[Index]))+qword(Carry);
   Carry:=Value shr 32;
   Dest[Index]:=Value and $ffffffff;
  end;
 end else begin
  Dest:=Source;
 end;                      
end;

procedure IntegerValueNOT(out Dest:TIntegerValue;const Source:TIntegerValue);
var Index:longint;
begin
 for Index:=0 to IntegerValueDWords-1 do begin
  Dest[Index]:=not Source[Index];
 end;
end;

procedure IntegerValueXOR(out Dest:TIntegerValue;const a,b:TIntegerValue);
var Index:longint;
begin
 for Index:=0 to IntegerValueDWords-1 do begin
  Dest[Index]:=a[Index] xor b[Index];
 end;
end;

procedure IntegerValueOR(out Dest:TIntegerValue;const a,b:TIntegerValue);
var Index:longint;
begin
 for Index:=0 to IntegerValueDWords-1 do begin
  Dest[Index]:=a[Index] or b[Index];
 end;
end;

procedure IntegerValueAND(out Dest:TIntegerValue;const a,b:TIntegerValue);
var Index:longint;
begin
 for Index:=0 to IntegerValueDWords-1 do begin
  Dest[Index]:=a[Index] and b[Index];
 end;
end;

procedure IntegerValueShiftLeftInternal(out Dest:TIntegerValue;const Source:TIntegerValue;const Shift:longint);
var Index,LowOffset,HighOffset,LowShift,HighShift,Offset:longint;
    Value:longword;
begin
 if (Shift and 31)<>0 then begin
  LowOffset:=(Shift-1) shr 5;
  HighOffset:=LowOffset+1;
  LowShift:=Shift-(LowOffset shl 5);
  HighShift:=32-LowShift;
  for Index:=0 to IntegerValueDWords-2 do begin
   Dest[Index]:=0;
  end;
  Dest[IntegerValueDWords-1]:=Source[IntegerValueDWords-HighOffset] shl LowShift;
  for Index:=(IntegerValueDWords-1)-HighOffset downto 0 do begin
   Value:=Source[Index];
   Dest[Index+LowOffset]:=Dest[Index+LowOffset] or (Value shl LowShift);
   Dest[Index+HighOffset]:=Dest[Index+HighOffset] or (Value shr HighShift);
  end;
 end else begin
  Offset:=Shift shr 5;
  for Index:=IntegerValueDWords-1 downto Offset do begin
   Dest[Index]:=Source[Index-Offset];
  end;
  for Index:=0 to Offset-1 do begin
   Dest[Index]:=0;
  end;
 end;
end;

procedure IntegerValueUnsignedShiftRightInternal(out Dest:TIntegerValue;const Source:TIntegerValue;const Shift:longint);
var Index,LowOffset,HighOffset,LowShift,HighShift,Offset:longint;
    Value:longword;
begin
 if (Shift and 31)<>0 then begin
  HighOffset:=(Shift-1) shr 5;
  LowOffset:=HighOffset+1;
  HighShift:=Shift-(HighOffset shl 5);
  LowShift:=32-HighShift;
  Dest[0]:=Source[HighOffset] shr HighShift;
  for Index:=1 to IntegerValueDWords-1 do begin
   Dest[Index]:=0;
  end;
  for Index:=LowOffset to IntegerValueDWords-1 do begin
   Value:=Source[Index];
   Dest[Index-HighOffset]:=Dest[Index-HighOffset] or (Value shr HighShift);
   Dest[Index-LowOffset]:=Dest[Index-LowOffset] or (Value shl LowShift);
  end;
 end else begin
  Offset:=Shift shr 5;
  for Index:=IntegerValueDWords-1 downto Offset do begin
   Dest[Index-Offset]:=Source[Index];
  end;
  for Index:=IntegerValueDWords-Offset to IntegerValueDWords-1 do begin
   Dest[Index]:=0;
  end;
 end;
end;

procedure IntegerValueShiftLeft(out Dest:TIntegerValue;const Source:TIntegerValue;const Shift:longint);
var Index,ShiftOffset,BitShift,InverseBitShift:longint;
    Current,Next:longword;
begin
 case Shift of
  1..IntegerValueBits-1:begin
   ShiftOffset:=Shift shr 5;
   BitShift:=Shift and 31;
   InverseBitShift:=(32-BitShift) and 31;
   if ShiftOffset=0 then begin
    if BitShift=0 then begin
     Dest:=Source;
    end else begin
     Next:=0;
     for Index:=0 to IntegerValueDWords-1 do begin
      Current:=Source[Index];
      Dest[Index]:=(Current shl BitShift) or Next;
      Next:=Current shr InverseBitShift;
     end;
    end;
   end else begin
    if BitShift=0 then begin
     for Index:=ShiftOffset to IntegerValueDWords-1 do begin
      Dest[Index]:=Source[Index-ShiftOffset];
     end;
    end else begin
     Next:=0;
     for Index:=ShiftOffset to IntegerValueDWords-1 do begin
      Current:=Source[Index-ShiftOffset];
      Dest[Index]:=(Current shl BitShift) or Next;
      Next:=Current shr InverseBitShift;
     end;
    end;
    for Index:=0 to ShiftOffset-1 do begin
     Dest[Index]:=0;
    end;
   end;
  end;
  IntegerValueBits..$7fffffff:begin
   for Index:=0 to IntegerValueDWords-1 do begin
    Dest[Index]:=0;
   end;
  end
  else begin
   Dest:=Source;
  end;
 end;
end;

procedure IntegerValueShiftRight(out Dest:TIntegerValue;const Source:TIntegerValue;const Shift:longint);
var Index,ShiftOffset,BitShift,InverseBitShift:longint;
    SignMask,Current,Next:longword;
begin
 case Shift of
  1..IntegerValueBits-1:begin
   ShiftOffset:=Shift shr 5;
   BitShift:=Shift and 31;
   InverseBitShift:=(32-BitShift) and 31;
   SignMask:=longword(-(Source[IntegerValueDWords-1] shr 31));
   if ShiftOffset=0 then begin
    if BitShift=0 then begin
     Dest:=Source;
    end else begin
     Next:=SignMask shl InverseBitShift;
     for Index:=IntegerValueDWords-1 downto 0 do begin
      Current:=Source[Index];
      Dest[Index]:=(Current shr BitShift) or Next;
      Next:=Current shl InverseBitShift;
     end;
    end;
   end else begin
    if BitShift=0 then begin
     for Index:=ShiftOffset to IntegerValueDWords-1 do begin
      Dest[Index-ShiftOffset]:=Source[Index];
     end;
    end else begin
     Next:=SignMask shl InverseBitShift;
     for Index:=IntegerValueDWords-1 downto ShiftOffset do begin
      Current:=Source[Index];
      Dest[Index-ShiftOffset]:=(Current shr BitShift) or Next;
      Next:=Current shl InverseBitShift;
     end;
    end;
    for Index:=IntegerValueDWords-ShiftOffset to IntegerValueDWords-1 do begin
     Dest[Index]:=SignMask;
    end;
   end;
  end;
  IntegerValueBits..$7fffffff:begin
   for Index:=0 to IntegerValueDWords-1 do begin
    Dest[Index]:=0;
   end;
  end
  else begin
   Dest:=Source;
  end;
 end;
end;

procedure IntegerValueUnsignedShiftRight(out Dest:TIntegerValue;const Source:TIntegerValue;const Shift:longint);
var Index,ShiftOffset,BitShift,InverseBitShift:longint;
    Current,Next:longword;
begin
 case Shift of
  1..IntegerValueBits-1:begin
   ShiftOffset:=Shift shr 5;
   BitShift:=Shift and 31;
   InverseBitShift:=(32-BitShift) and 31;
   if ShiftOffset=0 then begin
    if BitShift=0 then begin
     Dest:=Source;
    end else begin
     Next:=0;
     for Index:=IntegerValueDWords-1 downto 0 do begin
      Current:=Source[Index];
      Dest[Index]:=(Current shr BitShift) or Next;
      Next:=Current shl InverseBitShift;
     end;
    end;
   end else begin
    if BitShift=0 then begin
     for Index:=ShiftOffset to IntegerValueDWords-1 do begin
      Dest[Index-ShiftOffset]:=Source[Index];
     end;
    end else begin
     Next:=0;
     for Index:=IntegerValueDWords-1 downto ShiftOffset do begin
      Current:=Source[Index];
      Dest[Index-ShiftOffset]:=(Current shr BitShift) or Next;
      Next:=Current shl InverseBitShift;
     end;
    end;
    for Index:=IntegerValueDWords-ShiftOffset to IntegerValueDWords-1 do begin
     Dest[Index]:=0;
    end;
   end;
  end;
  IntegerValueBits..$7fffffff:begin
   for Index:=0 to IntegerValueDWords-1 do begin
    Dest[Index]:=0;
   end;
  end
  else begin
   Dest:=Source;
  end;
 end;
end;

procedure IntegerValueMulReference(out Dest:TIntegerValue;const a,b:TIntegerValue);
var i,j,k:longint;
    Value32,Carry:longword;
    Value64,Value:qword;
    Temp:array[0..(IntegerValueDWords*2)-1] of longword;
    Negative,NegativeA,NegativeB:boolean;
    TempA,TempB:TIntegerValue;
    WorkA,WorkB:PIntegerValue;
begin
 NegativeA:=(a[IntegerValueDWords-1] and longword($80000000))<>0;
 NegativeB:=(b[IntegerValueDWords-1] and longword($80000000))<>0;
 if NegativeA then begin
  IntegerValueNeg(TempA,a);
  WorkA:=@TempA;
 end else begin
  WorkA:=@a;
 end;
 if NegativeB then begin
  IntegerValueNeg(TempB,b);
  WorkB:=@TempB;
 end else begin
  WorkB:=@b;
 end;
 Negative:=NegativeA<>NegativeB;
 for i:=0 to (IntegerValueDWords*2)-1 do begin
  Temp[i]:=0;
 end;
 for i:=0 to IntegerValueDWords-1 do begin
  Value32:=WorkA^[i];
  if Value32<>0 then begin
   Value64:=Value32;
   Carry:=0;
   for j:=0 to IntegerValueDWords-1 do begin
    k:=i+j;
    Value:=qword(qword(Value64*WorkB^[j])+Temp[k])+Carry;
    Temp[k]:=longword(Value and $ffffffff);
    Carry:=longword(Value shr 32);
   end;
   Temp[i+IntegerValueDWords]:=Carry;
  end;
 end;
 if Negative then begin
  for i:=0 to IntegerValueDWords-1 do begin
   TempA[i]:=Temp[i];
  end;
  IntegerValueNeg(Dest,TempA);
 end else begin
  for i:=0 to IntegerValueDWords-1 do begin
   Dest[i]:=Temp[i];
  end;
 end;
end;

procedure IntegerValueMul(out Dest:TIntegerValue;const a,b:TIntegerValue);
var LimbIndex,BitIndex,ShiftCount:longint;
    Value:longword;
    Negative,NegativeA,NegativeB:boolean;
    Temp,NewTemp,TempResult,TempB:TIntegerValue;
    Work:PIntegerValue;
begin
 NegativeA:=(a[IntegerValueDWords-1] and longword($80000000))<>0;
 NegativeB:=(b[IntegerValueDWords-1] and longword($80000000))<>0;
 if NegativeA then begin
  IntegerValueNeg(Temp,a);
 end else begin
  Temp:=a;
 end;
 if NegativeB then begin
  IntegerValueNeg(TempB,b);
  Work:=@TempB;
 end else begin
  Work:=@b;
 end;
 Negative:=NegativeA<>NegativeB;
 for LimbIndex:=0 to IntegerValueDWords-1 do begin
  TempResult[LimbIndex]:=0;
 end;
 ShiftCount:=0;
 for LimbIndex:=0 to IntegerValueDWords-1 do begin
  Value:=Work^[LimbIndex];
  if Value<>0 then begin
   for BitIndex:=0 to 31 do begin
    if (Value and (longword(1) shl BitIndex))<>0 then begin
     if ShiftCount<>0 then begin
      IntegerValueShiftLeftInternal(NewTemp,Temp,ShiftCount);
      Temp:=NewTemp;
      ShiftCount:=0;
     end;
     IntegerValueAdd(NewTemp,TempResult,Temp);
     TempResult:=NewTemp;
    end;
    inc(ShiftCount);
   end;
  end else begin
   inc(ShiftCount,32);
  end;
 end;
 if Negative then begin
  IntegerValueNeg(Dest,TempResult);
 end else begin
  Dest:=TempResult;
 end;
end;

procedure IntegerValueDiv(out Dest:TIntegerValue;const a,b:TIntegerValue;const Remainder:PIntegerValue=nil);
var Comparsion,LimbIndex:longint;
    Negative,NegativeA,NegativeB:boolean;
    Temp,Denominator,Dividend,Current,Quotient:TIntegerValue;
begin
 NegativeA:=(a[IntegerValueDWords-1] and longword($80000000))<>0;
 NegativeB:=(b[IntegerValueDWords-1] and longword($80000000))<>0;
 if NegativeA then begin
  IntegerValueNeg(Dividend,a);
 end else begin
  Dividend:=a;
 end;
 if NegativeB then begin
  IntegerValueNeg(Denominator,b);
 end else begin
  Denominator:=b;
 end;
 Negative:=NegativeA<>NegativeB;
 Comparsion:=IntegerValueUnsignedCompare(Denominator,Dividend);
 if Comparsion>0 then begin
  for LimbIndex:=0 to IntegerValueDWords-1 do begin
   Dest[LimbIndex]:=0;
  end;
  if assigned(Remainder) then begin
   Remainder^:=a;
  end;
  exit;
 end else if Comparsion=0 then begin
  if Negative then begin
   for LimbIndex:=0 to IntegerValueDWords-1 do begin
    Dest[LimbIndex]:=$ffffffff;
   end;
  end else begin
   Dest[0]:=1;
   for LimbIndex:=1 to IntegerValueDWords-1 do begin
    Dest[LimbIndex]:=0;
   end;
  end;
  if assigned(Remainder) then begin
   for LimbIndex:=0 to IntegerValueDWords-1 do begin
    Remainder^[LimbIndex]:=0;
   end;
  end;
 end else begin
  for LimbIndex:=0 to IntegerValueDWords-1 do begin
   Quotient[LimbIndex]:=0;
  end;
  Current[0]:=1;
  for LimbIndex:=1 to IntegerValueDWords-1 do begin
   Current[LimbIndex]:=0;
  end;
  while IntegerValueUnsignedCompare(Denominator,Dividend)<=0 do begin
   IntegerValueShiftLeftInternal(Temp,Denominator,1);
   Denominator:=Temp;
   IntegerValueShiftLeftInternal(Temp,Current,1);
   Current:=Temp;
  end;
  IntegerValueUnsignedShiftRightInternal(Temp,Denominator,1);
  Denominator:=Temp;
  IntegerValueUnsignedShiftRightInternal(Temp,Current,1);
  Current:=Temp;
  while not IntegerValueIsZero(Current) do begin
   if IntegerValueUnsignedCompare(Dividend,Denominator)>=0 then begin
    IntegerValueSub(Temp,Dividend,Denominator);
    Dividend:=Temp;
    for LimbIndex:=0 to IntegerValueDWords-1 do begin
     Quotient[LimbIndex]:=Quotient[LimbIndex] or Current[LimbIndex];
    end;
   end;
   IntegerValueUnsignedShiftRightInternal(Temp,Denominator,1);
   Denominator:=Temp;
   IntegerValueUnsignedShiftRightInternal(Temp,Current,1);
   Current:=Temp;
  end;
  if assigned(Remainder) then begin
   Remainder^:=Dividend;
  end;
  if Negative then begin
   IntegerValueNeg(Dest,Quotient);
  end else begin
   Dest:=Quotient;
  end;
 end;
end;

procedure IntegerValueModulo(out Dest:TIntegerValue;const a,b:TIntegerValue);
var c,d:TIntegerValue;
begin
 // a mod b = a-(floor(a/b)*b)
 IntegerValueDiv(c,a,b);
 IntegerValueMul(d,c,b);
 IntegerValueSub(Dest,a,d);
end;

procedure IntegerValueSQRT(out Dest:TIntegerValue;const Source:TIntegerValue;const Remainder:PIntegerValue=nil);
var Number,TempResult,Temp,Bit,NewTemp:TIntegerValue;
begin
 if (Source[IntegerValueDWords-1] and longword($80000000))<>0 then begin
  IntegerValueNeg(Number,Source);
 end else begin
  Number:=Source;
 end;
 IntegerValueSetQWord(TempResult,0);
 IntegerValueSetQWord(Temp,1);
 IntegerValueShiftLeftInternal(Bit,Temp,(SizeOf(TIntegerValue)*8)-2);
 while IntegerValueUnsignedCompare(Bit,Number)>0 do begin
  IntegerValueUnsignedShiftRightInternal(Temp,Bit,2);
  Bit:=Temp;
 end;
 while not IntegerValueIsZero(Bit) do begin
  IntegerValueAdd(Temp,TempResult,Bit);
  if IntegerValueUnsignedCompare(Number,Temp)>=0 then begin
   IntegerValueSub(NewTemp,Number,Temp);
   Number:=NewTemp;
   IntegerValueUnsignedShiftRightInternal(NewTemp,TempResult,1);
   IntegerValueAdd(TempResult,NewTemp,Bit);
  end else begin
   IntegerValueUnsignedShiftRightInternal(NewTemp,TempResult,1);
   TempResult:=NewTemp;
  end;
  IntegerValueUnsignedShiftRightInternal(NewTemp,Bit,2);
  Bit:=NewTemp;
 end;
 Dest:=TempResult;
end;

procedure IntegerValueParse(out Dest:TIntegerValue;const s:ansistring;const StartPosition:longint=1);
var i,j,k:longint;
    Negative:boolean;
    TempResult,Temp,Base,Digit:TIntegerValue;
begin
 IntegerValueSetQWord(TempResult,0);
 j:=StartPosition;
 k:=length(s);
 while (j<=k) and (s[j] in [#1..#32]) do begin
  inc(j);
 end;
 Negative:=false;
 if (j<=k) and (s[j]='-') then begin
  Negative:=true;
  inc(j);
 end else if (j<=k) and (s[j]='+') then begin
  inc(j);
 end;
 if s[j]='0' then begin
  inc(j);
  case s[j] of
   'x','X','h','H':begin
    for i:=j+1 to k do begin
     case s[i] of
      '0'..'9':begin
       IntegerValueSetQWord(Digit,byte(ansichar(s[i]))-byte(ansichar('0')));
       IntegerValueShiftLeftInternal(Temp,TempResult,4);
       IntegerValueAdd(TempResult,Temp,Digit);
      end;
      'a'..'f':begin
       IntegerValueSetQWord(Digit,(byte(ansichar(s[i]))-byte(ansichar('a')))+$a);
       IntegerValueShiftLeftInternal(Temp,TempResult,4);
       IntegerValueAdd(TempResult,Temp,Digit);
      end;
      'A'..'F':begin
       IntegerValueSetQWord(Digit,(byte(ansichar(s[i]))-byte(ansichar('A')))+$a);
       IntegerValueShiftLeftInternal(Temp,TempResult,4);
       IntegerValueAdd(TempResult,Temp,Digit);
      end;
      else begin
       break;
      end;
     end;
    end;
   end;
   'o','O','q','Q':begin
    for i:=j+1 to k do begin
     case s[i] of
      '0'..'7':begin
       IntegerValueSetQWord(Digit,byte(ansichar(s[i]))-byte(ansichar('0')));
       IntegerValueShiftLeftInternal(Temp,TempResult,3);
       IntegerValueAdd(TempResult,Temp,Digit);
      end;
      else begin
       break;
      end;
     end;
    end;
   end;
   'b','B','y','Y':begin
    for i:=j+1 to k do begin
     case s[i] of
      '0'..'1':begin
       IntegerValueSetQWord(Digit,byte(ansichar(s[i]))-byte(ansichar('0')));
       IntegerValueShiftLeftInternal(Temp,TempResult,1);
       IntegerValueAdd(TempResult,Temp,Digit);
      end;
      else begin
       break;
      end;
     end;
    end;
   end;
   'd','D','t','T':begin
    IntegerValueSetQWord(Base,10);
    for i:=j+1 to k do begin
     if s[i] in ['0'..'9'] then begin
      IntegerValueSetQWord(Digit,byte(ansichar(s[i]))-byte(ansichar('0')));
      IntegerValueMul(Temp,TempResult,Base);
      IntegerValueAdd(TempResult,Temp,Digit);
     end else begin
      break;
     end;
    end;
   end;
   else begin
    IntegerValueSetQWord(Base,10);
    for i:=j to k do begin
     if s[i] in ['0'..'9'] then begin
      IntegerValueSetQWord(Digit,byte(ansichar(s[i]))-byte(ansichar('0')));
      IntegerValueMul(Temp,TempResult,Base);
      IntegerValueAdd(TempResult,Temp,Digit);
     end else begin
      break;
     end;
    end;
   end;
  end;
 end else begin
  IntegerValueSetQWord(Base,10);
  for i:=j to k do begin
   if s[i] in ['0'..'9'] then begin
    IntegerValueSetQWord(Digit,byte(ansichar(s[i]))-byte(ansichar('0')));
    IntegerValueMul(Temp,TempResult,Base);
    IntegerValueAdd(TempResult,Temp,Digit);
   end else begin
    break;
   end;
  end;
 end;
 if Negative then begin
  IntegerValueNeg(Dest,TempResult);
 end else begin
  Dest:=TempResult;
 end;
end;

function IntegerValueToStr(const Source:TIntegerValue):ansistring;
var Temp,NewTemp,OtherTemp,Base,Digit:TIntegerValue;
    Negative:boolean;
begin
 result:='';
 Negative:=(Source[IntegerValueDWords-1] and longword($80000000))<>0;
 if Negative then begin
  IntegerValueNeg(Temp,Source);
 end else begin
  Temp:=Source;
 end;
 if IntegerValueIsZero(Temp) then begin
  result:='0';
 end else begin
  IntegerValueSetQWord(Base,10);
  while not IntegerValueIsZero(Temp) do begin
   IntegerValueDiv(NewTemp,Temp,Base);
   IntegerValueMul(OtherTemp,NewTemp,Base);
   IntegerValueSub(Digit,Temp,OtherTemp);
   Temp:=NewTemp;
   result:=ansichar(byte(byte(ansichar('0'))+Digit[0]))+result;
  end;
 end;
 if Negative then begin
  result:='-'+result;
 end;
end;

function IntegerValueToHex(const Source:TIntegerValue):ansistring;
var Temp,NewTemp:TIntegerValue;
    Negative:boolean;
begin
 result:='';
 Negative:=(Source[IntegerValueDWords-1] and longword($80000000))<>0;
 if Negative then begin
  IntegerValueNeg(Temp,Source);
 end else begin
  Temp:=Source;
 end;
 if IntegerValueIsZero(Temp) then begin
  result:='0';
 end else begin
  while not IntegerValueIsZero(Temp) do begin
   if (Temp[0] and $f)<10 then begin
    result:=ansichar(byte(byte(ansichar('0'))+(Temp[0] and $f)))+result;
   end else begin
    result:=ansichar(byte(byte(ansichar('a'))+((Temp[0] and $f)-$a)))+result;
   end;
   IntegerValueUnsignedShiftRightInternal(NewTemp,Temp,4);
   Temp:=NewTemp;
  end;
 end;
 result:='0x'+result;
 if Negative then begin
  result:='-'+result;
 end;
end;

var a,b,c:TIntegerValue;
begin

 writeln;
 IntegerValueSetInt64(a,65536*4);
 IntegerValueSetInt64(b,-65536*2);
 IntegerValueMul(c,a,b);
 writeln(int64(pointer(@c[0])^));
 IntegerValueMulReference(c,a,b);
 writeln(int64(pointer(@c[0])^));

 writeln;
 IntegerValueSetInt64(a,10);
 IntegerValueSetInt64(b,8);
 IntegerValueDiv(c,a,b,@b);
 writeln(int64(pointer(@c[0])^));
 writeln(int64(pointer(@b[0])^));

 writeln;
 IntegerValueParse(a,'0xffffffffffffffff');
 writeln(IntegerValueToStr(a));
 writeln(IntegerValueToHex(a));

 readln;
end.