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.