sdpLogic.pas

// Íàáîð ïðîöåäóð äëÿ âûïîëíåíèÿ ëîãè÷åñêèõ îïåðàöèé íàä ïîðÿäêîâûìè òèïàìè.
// Âåðñèÿ äëÿ Delphi 5 è 32-õ ðàçðÿäíûõ ïðîöåññîðîâ.
// Àâòîð: Ñèäîðîâ Ä.Ï.

unit sdpLogic;

interface

uses
  sdpBigint;

// Âîçâðàùàåò íîìåð ñòàðøåãî íåíóëåâîãî áèòà (íóìåðàöèÿ íà÷èíàåòñÿ ñ 0).
// Åñëè X = 0, òî âîçâðàùàåò -1.
function HighestBit(X: Byte): Integer; overload;
function HighestBit(X: Shortint): Integer; overload;
function HighestBit(X: Word): Integer; overload;
function HighestBit(X: Smallint): Integer; overload;
function HighestBit(X: Cardinal): Integer; overload;
function HighestBit(X: Integer): Integer; overload;
function HighestBit(X: Int64): Integer; overload;
function HighestBit(const X: TBigint): Integer; overload;

// Âîçâðàùàåò íîìåð ìëàäøåãî íåíóëåâîãî áèòà (íóìåðàöèÿ íà÷èíàåòñÿ ñ 0).
// Åñëè X = 0, òî âîçâðàùàåò -1.
function LowestBit(X: Shortint): Integer; overload;
function LowestBit(X: Byte): Integer; overload;
function LowestBit(X: Smallint): Integer; overload;
function LowestBit(X: Word): Integer; overload;
function LowestBit(X: Integer): Integer; overload;
function LowestBit(X: Cardinal): Integer; overload;
function LowestBit(X: Int64): Integer; overload;
function LowestBit(const X: TBigint): Integer; overload;

procedure ShiftLeft(var X: TBigint; N: Byte);

// Ñðàâíåíèå àðãóìåíòîâ ïî àáñîëþòíîé âåëè÷èíå. Ðåçóëüòàò ðàâåí 1 åñëè A>B,
// 0 - A=B, -1 - A<B.
function CompareAbs(A, B: Shortint): Shortint; overload;
function CompareAbs(A, B: Smallint): Shortint; overload;
function CompareAbs(A, B: Integer): Shortint; overload;
function CompareAbs(A, B: Int64): Shortint; overload;
function CompareAbs(const A, B: TBigint): Shortint; overload;
function CompareAbs(const A: TBigint; B: Cardinal): Shortint; overload;

// Ñðàâíåíèå àðãóìåíòîâ. Ðåçóëüòàò ðàâåí 1 åñëè A>B, 0 - A=B, -1 - A<B.
function Compare(A, B: Byte): Shortint; overload;
function Compare(A, B: Shortint): Shortint; overload;
function Compare(A, B: Word): Shortint; overload;
function Compare(A, B: Smallint): Shortint; overload;
function Compare(A, B: Cardinal): Shortint; overload;
function Compare(A, B: Integer): Shortint; overload;
function Compare(A, B: Int64): Shortint; overload;
function Compare(const A, B: TBigint): Shortint; overload;

implementation

const
  BytesInWord     = SizeOf(Word);
  BytesInSmallint = SizeOf(Smallint);
  BytesInCardinal = SizeOf(Cardinal);
  BytesInInteger  = SizeOf(Integer);
  BytesInInt64    = SizeOf(Int64);

  BitsInByte     = 8;
  BitsInShortint = SizeOf(Shortint)*BitsInByte;
  BitsInWord     = BytesInWord*BitsInByte;
  BitsInSmallint = BytesInSmallint*BitsInByte;
  BitsInCardinal = BytesInCardinal*BitsInByte;
  BitsInInteger  = BytesInInteger*BitsInByte;
  BitsInInt64    = BytesInInt64*BitsInByte;

type
  PCardinal = ^Cardinal;

//     öåëÿõ ïîëó÷åíèÿ ìàêñèìàëüíîãî áûñòðîäåéñòâèÿ, âîïðåêè ïðèíöèïàì
// ïðîöåäóðíîãî ïðîãðàììèðîâàíèÿ, íåêîòîðûå ôðàãìåíòû êîäà ïîâòîðÿþòñÿ
// íåñêîëüêî ðàç âìåñòî òîãî, ÷òîáû âûçûâàòüñÿ êàê îòäåëüíàÿ ïðîöåäóðà.

function HighestBit(X: Byte): Integer;
asm
  movzx ecx, X
  mov   eax, -1
  bsr   eax, ecx
end;

function HighestBit(X: Shortint): Integer;
asm
  movzx ecx, X
  mov   eax, -1
  bsr   eax, ecx
end;

function HighestBit(X: Word): Integer;
asm
  movzx ecx, X
  mov   eax, -1
  bsr   eax, ecx
end;

function HighestBit(X: Smallint): Integer;
asm
  movzx ecx, X
  mov   eax, -1
  bsr   eax, ecx
end;

function HighestBit(X: Cardinal): Integer;
asm
  mov ecx, X
  mov eax, -1
  bsr eax, ecx
end;

function HighestBit(X: Integer): Integer;
asm
  mov ecx, X
  mov eax, -1
  bsr eax, ecx
end;

function HighestBit(X: Int64): Integer;
asm
  push esi
  lea  esi, X+BytesInCardinal               // esi = óêàçàòåëü íà ñòàðøóþ ÷àñòü
  mov  eax, -1
  bsr  eax, [esi]
  jz   @ZeroDWord                                          // Ñòàðøàÿ ÷àñòü = 0
  add  eax, BitsInCardinal
  jmp  @Exit
@ZeroDWord:
  sub  esi, BytesInCardinal                 // esi = óêàçàòåëü íà ìëàäøóþ ÷àñòü
  bsr  eax, [esi]
@Exit:
  pop  esi
end;

function HighestBit(const X: TBigint): Integer;
asm
  push  esi
  mov   esi, X+ofPtrDigits                   // esi = óêàçàòåëü íà ìëàäøèé áëîê
  movzx ecx, byte ptr (X+ofMSB)              // ecx = êîëè÷åñòâî áëîêîâ â ÷èñëå
  dec   ecx
  shl   ecx, 2              // ecx := ecx*4 - êîëè÷åñòâî áàéò äî ñòàðøåãî áëîêà
  add   esi, ecx                             // esi = óêàçàòåëü íà ñòàðøèé áëîê
  mov   eax, -1
  bsr   eax, [esi]
  jz    @Exit                                     // Ñòàðøèé áëîê = 0, òî X = 0
  shl   ecx, 3               // ecx := ecx*8 - êîëè÷åñòâî áèò äî ñòàðøåãî áëîêà
  add   eax, ecx
@Exit:
  pop esi
end;

// ****************************************************************************

function LowestBit(X: Shortint): Integer;
asm
  movzx ecx, X
  mov   eax, -1
  bsf   eax, ecx
end;

function LowestBit(X: Byte): Integer;
asm
  movzx ecx, X
  mov   eax, -1
  bsf   eax, ecx
end;

function LowestBit(X: Smallint): Integer;
asm
  movzx ecx, X
  mov   eax, -1
  bsf   eax, ecx
end;

function LowestBit(X: Word): Integer;
asm
  movzx ecx, X
  mov   eax, -1
  bsf   eax, ecx
end;

function LowestBit(X: Integer): Integer;
asm
  mov ecx, X
  mov eax, -1
  bsf eax, ecx
end;

function LowestBit(X: Cardinal): Integer;
asm
  mov ecx, X
  mov eax, -1
  bsf eax, ecx
end;

function LowestBit(X: Int64): Integer;
asm
  push esi
  lea  esi, X                               // esi = óêàçàòåëü íà ìëàäøóþ ÷àñòü
  mov  eax, -1
  bsf  eax, dword ptr [esi]
  jnz  @Exit                                              // Ìëàäøàÿ ÷àñòü <> 0
  add  esi, BytesInCardinal                 // esi = óêàçàòåëü íà ñòàðøóþ ÷àñòü
  bsf  eax, dword ptr [esi]
  jz   @Exit                                               // Ñòàðøàÿ ÷àñòü = 0
  add  eax, BitsInCardinal
@Exit:
  pop  esi
end;

function LowestBit(const X: TBigint): Integer;
asm
  push  esi
  mov   esi, X+ofPtrDigits                   // esi = óêàçàòåëü íà ìëàäøèé áëîê
  movzx ecx, byte ptr (X+ofMSB)              // ecx = êîëè÷åñòâî áëîêîâ â ÷èñëå
  mov   eax, -1
  xor   edx, edx                                  // Ñ÷åò÷èê îáðàáîòàííûõ áèòîâ
@NextBlock:
  bsf   eax, [esi]
  jnz   @BreakLoop                                       // Íàéäåí íåíóëîé áëîê
  add   esi, BytesInCardinal
  add   edx, BitsInCardinal
  loop  @NextBlock
  cmp   eax, -1                                                       // X = 0?
  je    @Exit
@BreakLoop:
  add   eax, edx
@Exit:
  pop   esi
end;

// ****************************************************************************

procedure ShiftLeft(var X: TBigint; N: Byte);
begin
//  HighestBit(TDigits(X.PtrDigits^)[X.MSB]);
end;

// ****************************************************************************

function CompareAbs(A, B: Shortint): Shortint;
begin
  A := Abs(A);
  B := Abs(B);
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function CompareAbs(A, B: Smallint): Shortint;
begin
  A := Abs(A);
  B := Abs(B);
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function CompareAbs(A, B: Integer): Shortint;
begin
  A := Abs(A);
  B := Abs(B);
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function CompareAbs(A, B: Int64): Shortint;
begin
  A := Abs(A);
  B := Abs(B);
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function CompareAbs(const A, B: TBigint): Shortint;
var
  PtrFirst, PtrSecond: PCardinal;
  Count: Byte;
begin
  // Çíàêè íàñ íå èíòåðåñóþò, ïîýòîìó ïðîâåðÿåì äëèíó
  if A.MSB = B.MSB then                                // Àðãóìåíòû îäíîé äëèíû
  begin
    PtrFirst := A.PtrDigits;
    PtrSecond := B.PtrDigits;
    Count := A.MSB;
    // Óñòàíàâëèâàåì óêàçàòåëü íà ñòàðøèé çíà÷àùèé áëîê
    Inc(PtrFirst, Count-1);
    Inc(PtrSecond, Count-1);
    // Ïðîèçâîäèì ïîáëî÷íîå ñðàâíåíèå
    while (PtrFirst^ = PtrSecond^) and (Count > 0) do
    begin
      Dec(PtrFirst);
      Dec(PtrSecond);
      Count := Count - 1;
    end;
    if Count = 0 then                           // Ñîâïàëè çíà÷åíèÿ âñåõ áëîêîâ
      Result := 0
    else                                        // Àðãóìåíòû óæå òî÷íî íå ðàâíû
      if PtrFirst^ > PtrSecond^ then Result := 1 else Result := -1;
  end
  else                     // Àðãóìåíòû ðàçíîé äëèíû, ïîýòîìó çàâåäîìî íå ðàâíû
    if A.MSB > B.MSB then Result := 1 else Result := -1;
end;

function CompareAbs(const A: TBigint; B: Cardinal): Shortint;
begin
  // Çíàê íàñ íå èíòåðåñóåò, ïðîâåðÿåì äëèíó
  if A.MSB = 1 then                                    // Àðãóìåíòû îäíîé äëèíû
  begin
    if PCardinal(A.PtrDigits)^ > B then
      Result := 1
    else
      if PCardinal(A.PtrDigits)^ = B then Result := 0 else Result := -1;
  end
  else                    // Àðãóìåíòû ðàçíîé äëèíû, ïîýòîìó çàâåäîìî |A| > |B|
    Result := 1;
end;

// ****************************************************************************

function Compare(A, B: Byte): Shortint;
begin
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function Compare(A, B: Shortint): Shortint;
begin
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function Compare(A, B: Word): Shortint;
begin
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function Compare(A, B: Smallint): Shortint;
begin
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function Compare(A, B: Cardinal): Shortint;
begin
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function Compare(A, B: Integer): Shortint;
begin
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function Compare(A, B: Int64): Shortint;
begin
  if A > B then
    Result := 1
  else
    if A = B then Result := 0 else Result := -1;
end;

function Compare(const A, B: TBigint): Shortint;
begin
  // Ïðîâåðÿåì çíàêè àðãóìåíòîâ
  if A.Sign > B.Sign then
  begin
    Result := 1;
    Exit;
  end;
  if A.Sign < B.Sign then
  begin
    Result := -1;
    Exit;
  end;
  // Àðãóìåíòû îäíîãî çíàêà, ïðîâåðÿåì äëèíó
  if A.MSB = B.MSB then                                // Àðãóìåíòû îäíîé äëèíû
  begin
    if A.Sign = -1 then                                         // A < 0, B < 0
      Result := -CompareAbs(A, B)
    else                                     // A = 0, B = 0 èíà÷å A > 0, B > 0
      if A.Sign = 0 then Result := 0 else Result := CompareAbs(A, B);
  end
  else                                                // Àðãóìåíòû ðàçíîé äëèíû
  begin
    // Çàâåäîìî A.Sign <> 0, èíà÷å áû ñîâïàëè è äëèíû àðãóìåíòîâ
    if A.Sign = -1 then                                         // A < 0, B < 0
      if A.MSB < B.MSB then Result := 1 else Result := -1
    else                                                        // A > 0, B > 0
      if A.MSB > B.MSB then Result := 1 else Result := -1;
  end;
end;

end.