implementation of unsigned for CP

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