unit LargeInt;
interface
type
PInt128 = ^UInt128;
UInt128 = packed record
private
function GetQuadPart(AIndex: Integer): LongWord;
procedure SetQuadPart(AIndex: Integer; const Value: LongWord);
public
Hi: UInt64;
Lo: UInt64;
function IsZero: Boolean;
procedure Inc(const AValue: UInt128);
function Multiply(const AValue: LongWord): UInt128;
function Divide(const AValue: LongWord; out ARemainder: LongWord): UInt128;
property QuadPart[AIndex: Integer]: LongWord read GetQuadPart write SetQuadPart;
end;
function ToUInt128(AHi, ALo: UInt64): UInt128;
implementation
function ToUInt128(AHi, ALo: UInt64): UInt128;
begin
Result.Hi := AHi;
Result.Lo := ALo;
end;
function AddWithCarry(const A, B: LongWord; var Carry: LongWord): LongWord;
var
R: UInt64;
begin
R := UInt64(A) + UInt64(B) + UInt64(Carry);
Carry := (R shr 32) and $1;
Result := LongWord(R);
end;
function MultiplyWithCarry(const A, B: LongWord; var Carry: LongWord): LongWord;
var
R: UInt64;
begin
// "Carry" here is a misnomer. A multiplication never generates a carry, since
// the product of two 32-bit values is a 64-bit value. But here we return
// only the lowest 32 bits, leaving the higher 32-bit in the "Carry".
R := UInt64(A) * UInt64(B) + UInt64(Carry);
Carry := (R shr 32);
Result := LongWord(R);
end;
function DivideWithRemainder(const A, B: LongWord; var Remainder: LongWord): LongWord;
var
A64: UInt64;
begin
A64 := (UInt64(Remainder) shl 32 or A);
Remainder := A64 mod B;
Result := A64 div B;
end;
// --- UInt128 -----------------------------------------------------------
function UInt128.GetQuadPart(AIndex: Integer): LongWord;
begin
Result := 0;
case AIndex of
3: Result := Self.Hi shr 32;
2: Result := Self.Hi;
1: Result := Self.Lo shr 32;
0: Result := Self.Lo;
end;
end;
procedure UInt128.SetQuadPart(AIndex: Integer; const Value: LongWord);
begin
case AIndex of
3: Self.Hi := (Self.Hi and $00000000FFFFFFFF) or (UInt64(Value) shl 32);
2: Self.Hi := (Self.Hi and $FFFFFFFF00000000) or Value;
1: Self.Lo := (Self.Lo and $00000000FFFFFFFF) or (UInt64(Value) shl 32);
0: Self.Lo := (Self.Lo and $FFFFFFFF00000000) or Value;
end;
end;
function UInt128.IsZero: Boolean;
begin
Result := (Self.Hi = 0) and (Self.Lo = 0);
end;
procedure UInt128.Inc(const AValue: UInt128);
var
LCarry: LongWord;
begin
LCarry := 0;
Self.QuadPart[0] := AddWithCarry(Self.QuadPart[0], AValue.QuadPart[0], LCarry);
Self.QuadPart[1] := AddWithCarry(Self.QuadPart[1], AValue.QuadPart[1], LCarry);
Self.QuadPart[2] := AddWithCarry(Self.QuadPart[2], AValue.QuadPart[2], LCarry);
Self.QuadPart[3] := AddWithCarry(Self.QuadPart[3], AValue.QuadPart[3], LCarry);
end;
function UInt128.Multiply(const AValue: LongWord): UInt128;
var
LCarry: LongWord;
begin
LCarry := 0;
Result.QuadPart[0] := MultiplyWithCarry(Self.QuadPart[0], AValue, LCarry);
Result.QuadPart[1] := MultiplyWithCarry(Self.QuadPart[1], AValue, LCarry);
Result.QuadPart[2] := MultiplyWithCarry(Self.QuadPart[2], AValue, LCarry);
Result.QuadPart[3] := MultiplyWithCarry(Self.QuadPart[3], AValue, LCarry);
end;
function UInt128.Divide(const AValue: LongWord; out ARemainder: LongWord): UInt128;
begin
ARemainder := 0;
Result.QuadPart[3] := DivideWithRemainder(Self.QuadPart[3], AValue, ARemainder);
Result.QuadPart[2] := DivideWithRemainder(Self.QuadPart[2], AValue, ARemainder);
Result.QuadPart[1] := DivideWithRemainder(Self.QuadPart[1], AValue, ARemainder);
Result.QuadPart[0] := DivideWithRemainder(Self.QuadPart[0], AValue, ARemainder);
end;
end.