Skip to content

Instantly share code, notes, and snippets.

@hodzanassredin

hodzanassredin/unsigned.mod

Last active June 15, 2023 15:39
Show Gist options
  • Save hodzanassredin/6db07b69451a21648c6a7d2c1903b878 to your computer and use it in GitHub Desktop.
Save hodzanassredin/6db07b69451a21648c6a7d2c1903b878 to your computer and use it in GitHub Desktop.
Download ZIP
implementation of unsigned for CP
Raw
unsigned.mod
MODULE CryptoUnsigned;
IMPORT SYSTEM, StdLog;
TYPE
UNSIGNED8 = BYTE;
UNSIGNED16 = SHORTINT;
UNSIGNED32 = INTEGER;
UNSIGNED64 = LONGINT;
CONST
UNSIGNED8_MIN = SHORT(SHORT(0));
UNSIGNED8_MAX = SHORT(SHORT(-1));
UNSIGNED16_MIN = SHORT(0);
UNSIGNED16_MAX = SHORT(-1);
UNSIGNED32_MIN = 0;
UNSIGNED32_MAX = -1;
UNSIGNED64_MIN = 0;
UNSIGNED64_MAX = 0FFFFFFFFFFFFFFFFL;
PROCEDURE[code] DivUnsignedInline8 (x, y: UNSIGNED8): UNSIGNED8
066H, 059H, (* pop cx *)
00FH, 0B6H, 0C0H, (* movzx eax, al *)
0F6H, 0F1H; (* div cl *)
PROCEDURE DivUnsigned8* (x, y: UNSIGNED8): UNSIGNED8;
BEGIN
RETURN DivUnsignedInline8(x,y);
END DivUnsigned8;
PROCEDURE [code] ModUnsignedInline8* (x, y: UNSIGNED8): UNSIGNED8
066H, 059H, (* pop cx *)
00FH, 0B6H, 0C0H, (* movzx eax, al *)
0F6H, 0F1H, (* div cl *)
00FH, 0B6H, 0C4H; (* movzx eax, ah *)
PROCEDURE ModUnsigned8* (x, y: UNSIGNED8): UNSIGNED8;
BEGIN
RETURN ModUnsignedInline8(x, y);
END ModUnsigned8;
PROCEDURE[code] DivUnsignedInline16 (x, y: UNSIGNED16): UNSIGNED16
066H, 059H, (* pop cx *)
066H, 0BAH, 000H, 000H, (* mov dx, 0 *)
066H, 0F7H, 0F1H; (* div cx *)
PROCEDURE DivUnsigned16* (x, y: UNSIGNED16): UNSIGNED16;
BEGIN
RETURN DivUnsignedInline16(x,y);
END DivUnsigned16;
PROCEDURE [code] ModUnsignedInline16* (x, y: UNSIGNED16): UNSIGNED16
066H, 059H, (* pop cx *)
066H, 0BAH, 000H, 000H, (* mov dx, 0 *)
066H, 0F7H, 0F1H, (* div cx *)
066H, 08BH, 0C2H; (* mov ax, dx *)
PROCEDURE ModUnsigned16* (x, y: UNSIGNED16): UNSIGNED16;
BEGIN
RETURN ModUnsignedInline16(x, y);
END ModUnsigned16;
PROCEDURE[code] DivUnsignedInline32 (x, y: UNSIGNED32): UNSIGNED32
059H, (* pop ecx *)
0BAH, 000H, 000H, 000H, 000H, (* mov edx, 0 *)
0F7H, 0F1H; (* div ecx *)
PROCEDURE DivUnsigned32* (x, y: UNSIGNED32): UNSIGNED32;
BEGIN
RETURN DivUnsignedInline32(x, y);
END DivUnsigned32;
PROCEDURE [code] ModUnsignedInline32* (x, y: UNSIGNED32): UNSIGNED32
059H, (* pop ecx *)
0BAH, 000H, 000H, 000H, 000H, (* mov edx, 0 *)
0F7H, 0F1H, (* div ecx *)
08BH, 0C2H; (* mov eax, edx *)
PROCEDURE [code] Bsr32Inline*(x: UNSIGNED32): INTEGER
00FH, 0BDH, 0C0H; (* bsr eax,eax *)
PROCEDURE Clz32*(x: UNSIGNED32): INTEGER;
BEGIN
IF x = 0 THEN RETURN 32 ELSE RETURN 31 - Bsr32Inline(x) END
END Clz32;
PROCEDURE ModUnsigned32* (x, y: UNSIGNED32): UNSIGNED32;
BEGIN
RETURN ModUnsignedInline32(x, y);
END ModUnsigned32;
PROCEDURE [code] LssUnsigned* (x, y: UNSIGNED32): BOOLEAN
059H, (* pop ecx *)
039H, 0C8H, (* cmp eax, ecx *)
00FH, 092H, 0C0H, (* setb al *)
00FH, 0B6H, 0C0H; (* movzx eax, al *)
PROCEDURE LeqUnsigned* (x, y: UNSIGNED32): BOOLEAN;
BEGIN
RETURN (x = y) OR LssUnsigned(x,y);
END LeqUnsigned;
PROCEDURE [code] GtrUnsigned* (x, y: UNSIGNED32): BOOLEAN
059H, (* pop ecx *)
039H, 0C1H, (* cmp ecx, eax *)
00FH, 092H, 0C0H, (* setb al *)
00FH, 0B6H, 0C0H; (* movzx eax,al *)
PROCEDURE GeqUnsigned* (x, y: UNSIGNED32): BOOLEAN;
BEGIN
RETURN (x = y) OR GtrUnsigned(x,y);
END GeqUnsigned;
PROCEDURE LSHUnsigned32* (x: UNSIGNED32; n : INTEGER): UNSIGNED32;
BEGIN
RETURN SYSTEM.LSH(x,n);
END LSHUnsigned32;
PROCEDURE[code] SHLDUnsignedInline64 (x: UNSIGNED64; n: UNSIGNED32): UNSIGNED64
059H, (* pop ecx *)
00FH, 0A5H, 0C2H, (* shld edx, eax, cl *)
0D3H, 0E0H; (* shl eax, cl *)
PROCEDURE[code] SHRDUnsignedInline64 (x: UNSIGNED64; n: UNSIGNED32): UNSIGNED64
059H, (* pop ecx *)
00FH, 0ADH, 0D0H, (* shrd eax,edx,cl *)
0D3H, 0EAH; (* shr edx,cl *)
PROCEDURE[code] GetUnsignedInline64 (low, high: UNSIGNED32): UNSIGNED64
05AH; (* pop edx *)
PROCEDURE[code] AddUnsignedInline64 (x, y: UNSIGNED64): UNSIGNED64
059H, (* pop ecx *)
001H, 0C8H, (* add eax, ecx *)
059H, (* pop ecx *)
011H, 0CAH; (* adc edx, ecx *)
PROCEDURE[code] SubUnsignedInline64 (x, y: UNSIGNED64): UNSIGNED64
059H, (* pop ecx *)
029H, 0C8H, (* sub eax, ecx *)
059H, (* pop ecx *)
019H, 0CAH; (* sbb edx, ecx *)
PROCEDURE[code] GetHighBitsUnsignedInline64 (x: UNSIGNED64): UNSIGNED32
089H, 0D0H; (*mov eax, edx*)
PROCEDURE LSHUnsigned64* (x: UNSIGNED64; n : INTEGER): UNSIGNED64;
BEGIN
IF n >= 0 THEN
IF n > 31 THEN
RETURN GetUnsignedInline64(0, SYSTEM.LSH(SYSTEM.VAL(INTEGER, x), n-32));
ELSE
RETURN SHLDUnsignedInline64(x,n);
END;
ELSE
IF n < -31 THEN
RETURN GetUnsignedInline64(SYSTEM.LSH(SYSTEM.VAL(INTEGER, x), n+32),0);
ELSE
RETURN SHRDUnsignedInline64(x,-n);
END;
END;
END LSHUnsigned64;
PROCEDURE LssUnsigned64* (x, y: UNSIGNED64): BOOLEAN;
VAR p,p2 : UNSIGNED32;
BEGIN
p := GetHighBitsUnsignedInline64(x);
p2 := GetHighBitsUnsignedInline64(y);
IF p = p2 THEN
p := SYSTEM.VAL(INTEGER, x);
p2 := SYSTEM.VAL(INTEGER, y);
END;
RETURN LssUnsigned(p, p2);
END LssUnsigned64;
PROCEDURE LeqUnsigned64* (x, y: UNSIGNED64): BOOLEAN;
BEGIN
RETURN (x = y) OR LssUnsigned64(x,y);
END LeqUnsigned64;
PROCEDURE GtrUnsigned64* (x, y: UNSIGNED64): BOOLEAN;
VAR p,p2 : UNSIGNED32;
BEGIN
p := GetHighBitsUnsignedInline64(x);
p2 := GetHighBitsUnsignedInline64(y);
IF p = p2 THEN
p := SYSTEM.VAL(INTEGER, x);
p2 := SYSTEM.VAL(INTEGER, y);
END;
RETURN GtrUnsigned(p, p2);
END GtrUnsigned64;
PROCEDURE GeqUnsigned64* (x, y: UNSIGNED64): BOOLEAN;
BEGIN
RETURN (x = y) OR GtrUnsigned64(x,y);
END GeqUnsigned64;
(* Count leading zeros in a binary representation of a given 64-bit integer number *)
PROCEDURE Clz64*(x: UNSIGNED64): INTEGER;
VAR p : UNSIGNED32;
BEGIN
p := GetHighBitsUnsignedInline64(x);
IF p # 0 THEN
RETURN Clz32(p);
ELSE
p := SYSTEM.VAL(INTEGER, x);
RETURN 32 + Clz32(p);
END;
RETURN 0;
END Clz64;
(*
Fast 64-bit unsigned integer division/modulo (Alexey Morozov)
*)
PROCEDURE DivModU64*(dividend, divisor: UNSIGNED64; VAR quotient, remainder: UNSIGNED64);
VAR m: INTEGER;
BEGIN
quotient := 0;
IF dividend = 0 THEN remainder := 0; RETURN; END;
IF LssUnsigned64(dividend, divisor) THEN remainder := dividend; RETURN; END;
m := Clz64(divisor) - Clz64(dividend);
ASSERT(m >= 0);
divisor := LSHUnsigned64(divisor,m);
WHILE m >= 0 DO
quotient := LSHUnsigned64(quotient,1);
IF GeqUnsigned64(dividend,divisor) THEN
INC(quotient);
DEC(dividend,divisor);
END;
divisor := LSHUnsigned64(divisor,-1);
DEC(m);
END;
remainder := dividend;
END DivModU64;
PROCEDURE DivUnsigned64* (x, y: UNSIGNED64): UNSIGNED64;
VAR quotient, remainder: UNSIGNED64;
BEGIN
DivModU64(x,y, quotient, remainder);
RETURN quotient;
END DivUnsigned64;
PROCEDURE ModUnsigned64* (x, y: UNSIGNED64): UNSIGNED64;
VAR quotient, remainder: UNSIGNED64;
BEGIN
DivModU64(x,y, quotient, remainder);
RETURN remainder;
END ModUnsigned64;
PROCEDURE MulUnsigned64(n,m: UNSIGNED64) : UNSIGNED64;
VAR res : UNSIGNED64;
BEGIN
res := 0;
WHILE m # 0 DO
IF 0 IN BITS(SYSTEM.VAL(INTEGER, m)) THEN
res := res + n
END;
n := LSHUnsigned64(n, 1);
m := LSHUnsigned64(m, -1)
END;
RETURN res;
END MulUnsigned64;
PROCEDURE LogUInt64 (val: UNSIGNED64);
VAR
str: ARRAY 21 OF CHAR;
i: INTEGER;
BEGIN
FOR i := 0 TO LEN(str) - 1 DO str[i] := "0"; END;
DEC(i);
str[i] := 0X;
DEC(i);
WHILE val # 0 DO
str[i] := CHR(ModUnsigned64(val, 10) + ORD('0'));
val := DivUnsigned64(val, 10);
DEC(i);
END;
StdLog.String(str$);
END LogUInt64;
PROCEDURE LogUInt32 (val: UNSIGNED32);
VAR
str: ARRAY 11 OF CHAR;
i: INTEGER;
BEGIN
FOR i := 0 TO LEN(str) - 1 DO str[i] := "0"; END;
DEC(i);
str[i] := 0X;
DEC(i);
WHILE val # 0 DO
str[i] := CHR(ModUnsigned32(val, 10) + ORD('0'));
val := DivUnsigned32(val, 10);
DEC(i);
END;
StdLog.String(str$);
END LogUInt32;
PROCEDURE LogUInt16 (val: UNSIGNED16);
VAR
str: ARRAY 6 OF CHAR;
i: INTEGER;
BEGIN
FOR i := 0 TO LEN(str) - 1 DO str[i] := "0"; END;
DEC(i);
str[i] := 0X;
DEC(i);
WHILE val # 0 DO
str[i] := CHR(ModUnsigned16(val, 10) + ORD('0'));
val := DivUnsigned16(val, 10);
DEC(i);
END;
StdLog.String(str$);
END LogUInt16;
PROCEDURE LogSet (val: SET;n:INTEGER);
VAR
str: ARRAY 33 OF CHAR;
i: INTEGER;
BEGIN
DEC(n);
FOR i := 0 TO n DO
IF i IN val THEN str[n - i] := '1' ELSE str[n - i] := '0' END;
END;
str[i] := 0X;
StdLog.String(str$);
END LogSet;
PROCEDURE LogUInt8 (val: UNSIGNED8);
VAR
str: ARRAY 4 OF CHAR;
i: INTEGER;
BEGIN
FOR i := 0 TO LEN(str) - 1 DO str[i] := "0"; END;
DEC(i);
str[i] := 0X;
DEC(i);
WHILE val # 0 DO
str[i] := CHR(ModUnsigned8(val, 10) + ORD('0'));
val := DivUnsigned8(val, 10);
DEC(i);
END;
StdLog.String(str$);
END LogUInt8;
PROCEDURE Log64 (val: LONGINT);
BEGIN
StdLog.String("AS INT: "); StdLog.Int(val); StdLog.Ln;
StdLog.String("AS UINT: "); LogUInt64(val); StdLog.Ln;
StdLog.String("AS BITS: ");
LogSet(BITS(GetHighBitsUnsignedInline64(val)), 32);
StdLog.Char(' ');
LogSet(BITS(SYSTEM.VAL(INTEGER, val)), 32)
END Log64;
PROCEDURE Log32 (val: INTEGER);
BEGIN
StdLog.String("AS INT: "); StdLog.Int(val); StdLog.Ln;
StdLog.String("AS UINT: "); LogUInt32(val); StdLog.Ln;
StdLog.String("AS BITS: "); LogSet(BITS(val),32);StdLog.Ln
END Log32;
PROCEDURE Log16 (val: SHORTINT);
BEGIN
StdLog.String("AS INT: "); StdLog.Int(val); StdLog.Ln;
StdLog.String("AS UINT: "); LogUInt16(val); StdLog.Ln;
StdLog.String("AS BITS: "); LogSet(BITS(val),16);StdLog.Ln
END Log16;
PROCEDURE Log8 (val: BYTE);
BEGIN
StdLog.String("AS INT: "); StdLog.Int(val); StdLog.Ln;
StdLog.String("AS UINT: "); LogUInt8(val); StdLog.Ln;
StdLog.String("AS BITS: "); LogSet(BITS(val), 8); StdLog.Ln
END Log8;
PROCEDURE Test64* ();
VAR t: UNSIGNED64;
BEGIN
StdLog.String("-----64 TESTS-------"); StdLog.Ln;
ASSERT(~LssUnsigned64(-1,2));StdLog.Ln;
ASSERT(GtrUnsigned64(-1,2));StdLog.Ln;
t := MAX(LONGINT);
StdLog.Int(UNSIGNED64_MAX);
StdLog.Int(t);
StdLog.Int(DivUnsigned64(t,10));
StdLog.Int(ModUnsigned64(t,10));
StdLog.Ln;
Log64(t); StdLog.Ln;
StdLog.String("------------"); StdLog.Ln;
Log64(AddUnsignedInline64(MulUnsigned64(t, 2), 1)); StdLog.Ln;
StdLog.String("------------"); StdLog.Ln;
Log64(SubUnsignedInline64(MulUnsigned64(t, 2), t));
StdLog.Ln
END Test64;
PROCEDURE Test32* ();
VAR t: UNSIGNED32;
BEGIN
StdLog.String("-----32 TESTS-------"); StdLog.Ln;
ASSERT(~LssUnsigned(-1, 2));StdLog.Ln;
ASSERT(GtrUnsigned(-1, 2));StdLog.Ln;
t := MAX(INTEGER);
StdLog.Int(UNSIGNED32_MAX);
StdLog.Int(t);
StdLog.Int(DivUnsigned32(t, 10));
StdLog.Int(ModUnsigned32(t, 10));
StdLog.Ln;
Log32(t); StdLog.Ln;
StdLog.String("------------"); StdLog.Ln;
Log32(t * 2 + 1); StdLog.Ln;
StdLog.String("------------"); StdLog.Ln;
Log32(t * 2 - t);
END Test32;
PROCEDURE Test16* ();
VAR t: UNSIGNED16;
BEGIN
StdLog.String("-----16 TESTS-------"); StdLog.Ln;
ASSERT(~LssUnsigned(-1,2));
ASSERT(GtrUnsigned(-1,2));
t := MAX(SHORTINT);
StdLog.Int(UNSIGNED16_MAX);
StdLog.Int(t);
StdLog.Int(DivUnsigned16(t,10));
StdLog.Int(ModUnsigned16(t,10));
StdLog.Ln;
Log16(t); StdLog.Ln;
StdLog.String("------------"); StdLog.Ln;
Log16(SHORT(t * 2 + 1)); StdLog.Ln;
StdLog.String("------------"); StdLog.Ln;
Log16(SHORT(t * 2 - t));
StdLog.Ln
END Test16;
PROCEDURE Test8* ();
VAR t: UNSIGNED8;
BEGIN
StdLog.String("-----8 TESTS-------"); StdLog.Ln;
ASSERT(~LssUnsigned(-1,2));
ASSERT(GtrUnsigned(-1,2));
t := MAX(BYTE);
StdLog.Int(UNSIGNED8_MAX);
StdLog.Int(t);
StdLog.Int(DivUnsigned8(t,10));
StdLog.Int(ModUnsigned8(t,10));
StdLog.Ln;
Log8(t); StdLog.Ln;
StdLog.String("------------"); StdLog.Ln;
Log8(SHORT(SHORT(t * 2 + 1))); StdLog.Ln;
StdLog.String("------------"); StdLog.Ln;
Log8(SHORT(SHORT(t * 2 - t)));
StdLog.Ln
END Test8;
PROCEDURE Test*();
VAR l,l2:LONGINT;low, high:INTEGER;
BEGIN
l := 12345;
l2 := 2;
StdLog.String(" AddUnsignedInline64 ");StdLog.Int(AddUnsignedInline64(l,l2));StdLog.Ln;
StdLog.String(" SubUnsignedInline64 ");StdLog.Int(SubUnsignedInline64(l,l2));StdLog.Ln;
StdLog.String(" LssUnsigned64 ");StdLog.Bool(LssUnsigned64(l,l2));StdLog.Ln;
StdLog.String(" DivUnsigned64 ");StdLog.Int(DivUnsigned64(l,10));
StdLog.String(" ModUnsigned64 ");StdLog.Int(ModUnsigned64(l,10));
Log64(UNSIGNED64_MAX);StdLog.Ln;
StdLog.String("Leading zeroes UNSIGNED64_MAX ");StdLog.Int(Clz64(UNSIGNED64_MAX)); StdLog.Ln;
l := GetUnsignedInline64(MAX(INTEGER),MAX(INTEGER));
l := LSHUnsigned64(l,-33);
high := GetHighBitsUnsignedInline64(l);
low := SYSTEM.VAL(INTEGER, l) ;
Log32(high);
Log32(low);
END Test;
END CryptoUnsigned.
CryptoUnsigned.Test;
CryptoUnsigned.Test64;
CryptoUnsigned.Test32;
CryptoUnsigned.Test16;
CryptoUnsigned.Test8;
-----8 TESTS-------
-1 127 12 7
AS INT: 127
AS UINT: 127
AS BITS: 01111111
------------
AS INT: -1
AS UINT: 255
AS BITS: 11111111
------------
AS INT: 127
AS UINT: 127
AS BITS: 01111111
-----16 TESTS-------
-1 32767 3276 7
AS INT: 32767
AS UINT: 32767
AS BITS: 0111111111111111
------------
AS INT: -1
AS UINT: 65535
AS BITS: 1111111111111111
------------
AS INT: 32767
AS UINT: 32767
AS BITS: 0111111111111111
-----32 TESTS-------
-1 2147483647 214748364 7
AS INT: 2147483647
AS UINT: 2147483647
AS BITS: 01111111111111111111111111111111
------------
AS INT: -1
AS UINT: 4294967295
AS BITS: 11111111111111111111111111111111
------------
AS INT: 2147483647
AS UINT: 2147483647
AS BITS: 01111111111111111111111111111111
-----64 TESTS-------
-1 9223372036854775807 922337203685477580 7
AS INT: 9223372036854775807
AS UINT: 09223372036854775807
AS BITS: 01111111111111111111111111111111 11111111111111111111111111111111
------------
AS INT: -1
AS UINT: 18446744073709551615
AS BITS: 11111111111111111111111111111111 11111111111111111111111111111111
------------
AS INT: 9223372036854775807
AS UINT: 09223372036854775807
AS BITS: 01111111111111111111111111111111 11111111111111111111111111111111
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment