source: branches/ByteArray/BigInt.pas

unit BigInt;

interface

uses
  Classes, SysUtils, Math;

type
  TArrayOfByte = array of Byte;

  TBigIntSize = Byte;

  { TBigInt }

  TBigInt = record
  private
    FData: array of Byte;
    function GetData(Index: TBigIntSize): Byte;
    function GetSize: TBigIntSize;
    procedure SetData(Index: TBigIntSize; AValue: Byte);
    procedure SetSize(AValue: TBigIntSize);
  public
    class operator Implicit(A: Byte): TBigInt;
    class operator Implicit(A: Word): TBigInt;
    class operator Implicit(A: ShortInt): TBigInt;
    class operator Implicit(A: Integer): TBigInt;
    class operator Implicit(A: QWord): TBigInt;
    class operator Implicit(A: Int64): TBigInt;
    class operator Implicit(A: TBigInt): UInt8; // Byte
    class operator Implicit(A: TBigInt): Int8; // ShortInt
    class operator Implicit(A: TBigInt): UInt16; // Word
    class operator Implicit(A: TBigInt): Int16; // SmallInt
    class operator Implicit(A: TBigInt): UInt32; // LongWord, DWord, Cardinal
    class operator Implicit(A: TBigInt): Int32; // Int32, LongInt
    class operator Implicit(A: TBigInt): UInt64; // QWord
    class operator Implicit(A: TBigInt): Int64;
    class operator Implicit(A: TBigInt): PByte;
    class operator Negative(A: TBigInt): TBigInt;
    class operator Inc(A: TBigInt) : TBigInt;
    class operator Dec(A: TBigInt) : TBigInt;
    class operator Add(A, B: TBigInt): TBigInt;
    class operator Subtract(A, B: TBigInt): TBigInt;
    class operator Equal(A, B: TBigInt): Boolean;
    class operator NotEqual(A, B: TBigInt): Boolean;
    class operator LessThan(A, B: TBigInt): Boolean;
    class operator LessThanOrEqual(A, B: TBigInt): Boolean;
    class operator GreaterThan(A, B: TBigInt): Boolean;
    class operator GreaterThanOrEqual(A, B: TBigInt): Boolean;
    class operator BitwiseXor(A, B: TBigInt): TBigInt;
    class operator BitwiseAnd(A, B: TBigInt): TBigInt;
    class operator BitwiseOr(A, B: TBigInt): TBigInt;
    class operator LeftShift(A: TBigInt; B: Integer): TBigInt;
    class operator RightShift(A: TBigInt; B: Integer): TBigInt;
    class operator Modulus(A, B: TBigInt): TBigInt;
    class operator IntDivide(A, B: TBigInt): TBigInt;
    procedure Shrink;
    function IsNegative: Boolean;
    function IsZero: Boolean;
    function IsPositive: Boolean;
    procedure Invert;
    procedure SetByteArray(AData: TArrayOfByte; ASize: TBigIntSize);
    procedure GetByteArray(var AData: TArrayOfByte; ASize: TBigIntSize);
    function Copy(Size: TBigIntSize): TBigInt; overload;
    function Copy: TBigInt; overload;
    property Size: TBigIntSize read GetSize write SetSize;
    property Data[Index: TBigIntSize]: Byte read GetData write SetData;
  end;

function TryStrToBigInt(const S: string; out I: TBigInt): Boolean;
function IntToStr(Value: TBigInt): string; overload;
function IntToHex(Value: TBigInt): string; overload;
function IntToHex(Value: TBigInt; Digits: Integer): string; overload;


implementation

resourcestring
  SUnsupportedByteSize = 'Unsupported byte size';
  SOutOfRange = 'Out of range';

const
   HexDigits: array[0..15] of Char = '0123456789ABCDEF';

function TryStrToBigInt(const S: string; out I: TBigInt): Boolean;
var
  Value: Int64;
begin
  Result := TryStrToInt64(S, Value);
  I := Value;
end;

function IntToHex(Value: TBigInt): string;
begin
  Result := '';
  while Value <> 0 do begin
    Result := HexDigits[Value and 15] + Result;
    Value := Value shr 4;
  end;
  if Result = '' then Result := '0';
end;

function IntToHex(Value: TBigInt; Digits: Integer): string;
var
  I: Integer;
begin
  if Digits = 0 then
    Digits := 1;
  Result := '';
  SetLength(Result, Digits);
  for I := 0 to Digits - 1 do
  begin
    Result[Digits - I] := HexDigits[Value and 15];
    Value := Value shr 4;
  end ;
  while Value <> 0 do begin
    Result := HexDigits[Value and 15] + Result;
    Value := Value shr 4;
  end;
end;

function IntToStr(Value: TBigInt): string;
begin
  Result := '';
  if Value < 0 then begin
    Value := -Value;
    while Value > 9 do begin
      Result := Chr(Ord('0') + (Value mod 10)) + Result;
      Value := Value div 10;
    end;
    Result := '-' + Chr(Ord('0') + (Value mod 10)) + Result;
  end else begin
    while Value > 9 do begin
      Result := Chr(Ord('0') + (Value mod 10)) + Result;
      Value := Value div 10;
    end;
    Result := Chr(Ord('0') + Value) + Result;
  end;
end;

{ TBigInt }

function TBigInt.GetSize: TBigIntSize;
begin
  Result := Length(FData);
end;

function TBigInt.GetData(Index: TBigIntSize): Byte;
begin
  if Index < Size then Result := FData[Index]
    else Result := 0;
end;

procedure TBigInt.SetData(Index: TBigIntSize; AValue: Byte);
begin
  if Index >= Integer(Size) then raise Exception.Create(SOutOfRange);
  FData[Index] := AValue;
end;

procedure TBigInt.SetSize(AValue: TBigIntSize);
var
  LastSize: TBigIntSize;
begin
  LastSize := GetSize;
  SetLength(FData, AValue);
  if AValue > LastSize then
    FillChar(FData[LastSize], AValue - LastSize, 0);
end;

class operator TBigInt.Implicit(A: Byte): TBigInt;
begin
  Result.Size := 1;
  Result.FData[0] := A;
end;

class operator TBigInt.Implicit(A: Word): TBigInt;
begin
  Result.Size := 2;
  PWord(@Result.FData[0])^ := A;
  Result.Shrink;
end;

class operator TBigInt.Implicit(A: ShortInt): TBigInt;
begin
  Result.Size := 1;
  PByte(@Result.FData[0])^ := A;
  Result.Shrink;
end;

class operator TBigInt.Implicit(A: Integer): TBigInt;
begin
  Result.Size := 4;
  PInteger(@Result.FData[0])^ := A;
  Result.Shrink;
end;

class operator TBigInt.Implicit(A: QWord): TBigInt;
begin
  Result.Size := 8;
  PQWord(@Result.FData[0])^ := A;
  Result.Shrink;
end;

class operator TBigInt.Implicit(A: Int64): TBigInt;
begin
  Result.Size := 8;
  PInt64(@Result.FData[0])^ := A;
  Result.Shrink;
end;

class operator TBigInt.Implicit(A: TBigInt): UInt8;
begin
  if A.Size = 1 then Result := A.FData[0]
    else raise Exception.Create(SUnsupportedByteSize);
end;

class operator TBigInt.Implicit(A: TBigInt): Int8;
begin
  if A.Size = 1 then Result := A.FData[0]
    else raise Exception.Create(SUnsupportedByteSize);
end;

class operator TBigInt.Implicit(A: TBigInt): UInt16;
begin
  if A.Size = 2 then Result := PUInt16(@A.FData[0])^
    else raise Exception.Create(SUnsupportedByteSize);
end;

class operator TBigInt.Implicit(A: TBigInt): Int16;
begin
  if A.Size = 2 then Result := PInt16(@A.FData[0])^
    else raise Exception.Create(SUnsupportedByteSize);
end;

class operator TBigInt.Implicit(A: TBigInt): Int32;
begin
  case A.Size of
    1: Result := PByte(@A.FData[0])^;
    2: Result := PWord(@A.FData[0])^;
    3: Result := PWord(@A.FData[0])^ or (PByte(@A.FData[2])^ shl 16);
    4: Result := PDWord(@A.FData[0])^;
    8: Result := PQWord(@A.FData[0])^;
    else raise Exception.Create(SUnsupportedByteSize);
  end;
end;

class operator TBigInt.Implicit(A: TBigInt): UInt32;
begin
  if A.Size = 4 then Result := PInt32(@A.FData[0])^
    else raise Exception.Create(SUnsupportedByteSize);
end;

class operator TBigInt.Implicit(A: TBigInt): UInt64;
begin
  if A.Size = 1 then Result := PUInt8(@A.FData[0])^
  else if A.Size = 2 then Result := PUInt16(@A.FData[0])^
  else if A.Size = 4 then Result := PUInt32(@A.FData[0])^
  else if A.Size = 8 then Result := PUInt64(@A.FData[0])^
  else raise Exception.Create(SUnsupportedByteSize);
end;

class operator TBigInt.Implicit(A: TBigInt): Int64;
begin
  if A.Size = 1 then Result := PInt8(@A.FData[0])^
  else if A.Size = 2 then Result := PInt16(@A.FData[0])^
  else if A.Size = 4 then Result := PInt32(@A.FData[0])^
  else if A.Size = 8 then Result := PInt64(@A.FData[0])^
  else raise Exception.Create(SUnsupportedByteSize);
end;

class operator TBigInt.Implicit(A: TBigInt): PByte;
begin
  if A.Size = 4 then Result := PByte(@PInteger(@A.FData[0])^)
    else raise Exception.Create(SUnsupportedByteSize);
end;

class operator TBigInt.Negative(A: TBigInt): TBigInt;
begin
  Result := A.Copy(A.Size);
  Result.Invert;
  Result := Result + 1;
end;

class operator TBigInt.Inc(A: TBigInt): TBigInt;
begin
  Result := A + 1;
end;

class operator TBigInt.Dec(A: TBigInt): TBigInt;
begin
  Result := A - 1;
end;

class operator TBigInt.Add(A, B: TBigInt): TBigInt;
var
  I: Integer;
  V: SmallInt;
  Carry: Byte;
  Size: Byte;
begin
  Size := Max(A.Size, B.Size);
  Result.Size := Size;
  Carry := 0;
  I := 0;
  while (I < Size) or (Carry > 0) do begin
    if I >= Result.Size then Result.Size := I + 1;
    V := A.Data[I] + B.Data[I] + Carry;
    if V >= 256 then begin
      Carry := 1;
    end else Carry := 0;
    Result.Data[I] := V and $ff;
    Inc(I);
  end;
end;

class operator TBigInt.Subtract(A, B: TBigInt): TBigInt;
var
  Size: TBigIntSize;
begin
  Size := Max(A.Size, B.Size);
  Result := A + -B;
  Result.Size := Size;
  Result.Shrink;
end;

class operator TBigInt.Equal(A, B: TBigInt): Boolean;
var
  I: Byte;
begin
  Result := A.Size = B.Size;
  if not Result then Exit;
  for I := 0 to A.Size - 1 do
    if A.FData[I] <> B.FData[I] then begin
      Result := False;
      Break;
    end;
end;

class operator TBigInt.NotEqual(A, B: TBigInt): Boolean;
var
  I: Byte;
begin
  Result := A.Size = B.Size;
  if not Result then Exit;
  for I := 0 to A.Size - 1 do
    if A.FData[I] <> B.FData[I] then begin
      Result := False;
      Break;
    end;
  Result := not Result;
end;

class operator TBigInt.LessThan(A, B: TBigInt): Boolean;
var
  Temp: TBigInt;
begin
  Temp := A - B;
  Result := Temp.IsNegative;
end;

class operator TBigInt.LessThanOrEqual(A, B: TBigInt): Boolean;
var
  Temp: TBigInt;
begin
  Temp := A - B;
  Result := Temp.IsNegative or Temp.IsZero;
end;

class operator TBigInt.GreaterThan(A, B: TBigInt): Boolean;
var
  Temp: TBigInt;
begin
  Temp := A - B;
  Result := Temp.IsPositive and not Temp.IsZero;
end;

class operator TBigInt.GreaterThanOrEqual(A, B: TBigInt): Boolean;
var
  Temp: TBigInt;
begin
  Temp := A - B;
  Result := Temp.IsPositive;
end;

class operator TBigInt.BitwiseXor(A, B: TBigInt): TBigInt;
var
  I: TBigIntSize;
begin
  Result.Size := Max(A.Size, B.Size);
  for I := 0 to Result.Size - 1 do
    Result.Data[I] := A.Data[I] xor B.Data[I];
  Result.Shrink;
end;

class operator TBigInt.BitwiseAnd(A, B: TBigInt): TBigInt;
var
  I: TBigIntSize;
begin
  Result.Size := Max(A.Size, B.Size);
  for I := 0 to Result.Size - 1 do
    Result.Data[I] := A.Data[I] and B.Data[I];
  Result.Shrink;
end;

class operator TBigInt.BitwiseOr(A, B: TBigInt): TBigInt;
var
  I: TBigIntSize;
begin
  Result.Size := Max(A.Size, B.Size);
  for I := 0 to Result.Size - 1 do
    Result.Data[I] := A.Data[I] or B.Data[I];
  Result.Shrink;
end;

class operator TBigInt.LeftShift(A: TBigInt; B: Integer): TBigInt;
var
  ByteShift: TBigIntSize;
  BitShift: Byte;
  I: Integer;
begin
  if (B and 7) = 0 then begin
    // Full byte shift
    ByteShift := B shr 3;
    Result.Size := A.Size + ByteShift;
    Move(A.FData[0], Result.FData[ByteShift], A.Size);
    FillChar(Result.FData[0], ByteShift, 0);
  end else begin
    // Partial byte shift
    ByteShift := B shr 3;
    BitShift := B - ByteShift;
    Result.Size := Result.Size + ByteShift + 1;
    for I := 0 to A.Size - 1 do begin
      Result.FData[I + ByteShift] := (A.FData[I] shl BitShift) and $ff;
      if I > 0 then Result.FData[I + ByteShift] := Result.FData[I + ByteShift] or (A.FData[I] shl BitShift shl 8);
    end;
  end;
  Result.Shrink;
end;

class operator TBigInt.RightShift(A: TBigInt; B: Integer): TBigInt;
var
  ByteShift: TBigIntSize;
  BitShift: Byte;
  I: Integer;
begin
  if (B and 7) = 0 then begin
    // Full byte shift
    ByteShift := B shr 3;
    Result.Size := A.Size - ByteShift;
    Move(A.FData[ByteShift], Result.FData[0], A.Size);
  end else begin
    // Partial byte shift
    ByteShift := B shr 3;
    BitShift := B - ByteShift;
    Result.Size := Result.Size - ByteShift;
    for I := 0 to A.Size - 1 do begin
      Result.FData[I] := (A.FData[I + ByteShift] shr BitShift) and $ff;
      if I < (A.Size - 1) then Result.FData[I] := Result.FData[I] or (((A.FData[I + ByteShift] shl 8) shr BitShift) and $ff);
    end;
  end;
  Result.Shrink;
end;

class operator TBigInt.Modulus(A, B: TBigInt): TBigInt;
begin

end;

class operator TBigInt.IntDivide(A, B: TBigInt): TBigInt;
begin

end;

procedure TBigInt.Shrink;
var
  I: Byte;
begin
  I := Size - 1;
  while (I > 0) and (FData[I] = 0) do
    Dec(I);
  Size := I + 1;
end;

function TBigInt.IsNegative: Boolean;
begin
  Result := (FData[Size - 1] and $80) = $80;
end;

function TBigInt.IsZero: Boolean;
var
  I: TBigIntSize;
begin
  Result := True;
  for I := 0 to Size - 1 do
    if FData[I] <> 0 then begin
      Result := False;
      Break;
    end;
end;

function TBigInt.IsPositive: Boolean;
begin
  Result := (FData[Size - 1] and $80) = 0;
end;

procedure TBigInt.Invert;
var
  I: Byte;
begin
  for I := 0 to Size - 1 do
    FData[I] := FData[I] xor $ff;
end;

procedure TBigInt.SetByteArray(AData: TArrayOfByte; ASize: TBigIntSize);
begin
  Size := ASize;
  Move(AData[0], FData[0], Size);
end;

procedure TBigInt.GetByteArray(var AData: TArrayOfByte; ASize: TBigIntSize);
begin
  SetLength(AData, ASize);
  Move(FData[0], AData[0], Size);
end;

function TBigInt.Copy(Size: TBigIntSize): TBigInt;
begin
  Result.Size := Size;
  case Result.Size of
    1: PByte(@Result.FData[0])^ := PByte(@FData[0])^;
    2: PWord(@Result.FData[0])^ := PWord(@FData[0])^;
    4: PDWord(@Result.FData[0])^ := PDWord(@FData[0])^;
    8: PQWord(@Result.FData[0])^ := PQWord(@FData[0])^;
    else Move(PByte(@FData[0])^, PByte(@Result.FData[0])^, Size);
  end;
end;

function TBigInt.Copy: TBigInt;
begin
  Result := Copy(Size);
end;

end.