WebSVN – Kolibri OS – Blame – /programs/network/ssh/mpint.inc

Rev	Author	Line No.	Line
6419	hidnplayr	1	; mpint.inc - Multi precision integer procedures
		2	;
9985	hidnplayr	3	; Copyright (C) 2015-2024 Jeffrey Amelynck
6419	hidnplayr	4	;
		5	; This program is free software: you can redistribute it and/or modify
		6	; it under the terms of the GNU General Public License as published by
		7	; the Free Software Foundation, either version 3 of the License, or
		8	; (at your option) any later version.
		9	;
		10	; This program is distributed in the hope that it will be useful,
		11	; but WITHOUT ANY WARRANTY; without even the implied warranty of
		12	; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
		13	; GNU General Public License for more details.
		14	;
		15	; You should have received a copy of the GNU General Public License
		16	; along with this program. If not, see .
		17
9090	hidnplayr	18	; Note:
6922	hidnplayr	19	;
9090	hidnplayr	20	; These procedures have been designed to work with unsigned integers.
6922	hidnplayr	21	; For compatibility reasons, the highest bit must always be 0.
		22	;
		23	; You have been warned!
		24
6419	hidnplayr	25	MPINT_MAX_LEN = MAX_BITS/8
		26
		27
6922	hidnplayr	28	;;===========================================================================;;
9070	hidnplayr	29	proc mpint_to_little_endian uses esi edi ecx, dst, src ;/////////////////////;;
6922	hidnplayr	30	;;---------------------------------------------------------------------------;;
		31	;? Convert big endian MPINT to little endian MPINT. ;;
		32	;;---------------------------------------------------------------------------;;
9070	hidnplayr	33	;> src = pointer to big endian MPINT ;;
		34	;> dst = pointer to buffer for little endian MPINT ;;
6922	hidnplayr	35	;;---------------------------------------------------------------------------;;
		36	;< eax = MPINT number length ;;
		37	;;===========================================================================;;
6419	hidnplayr	38
9070	hidnplayr	39	mov esi, [src]
		40	mov edi, [dst]
6419	hidnplayr	41	; Load length dword
		42	lodsd
		43	; Convert to little endian
		44	bswap eax
		45	stosd
		46	test eax, eax
		47	jz .zero
		48	; Copy data, convert to little endian meanwhile
		49	push eax
		50	add esi, eax
		51	dec esi
		52	mov ecx, eax
		53	std
		54	@@:
		55	lodsb
		56	mov byte[edi], al
		57	inc edi
		58	dec ecx
		59	jnz @r
9070	hidnplayr	60
6419	hidnplayr	61	cld
9070	hidnplayr	62	pop eax
6419	hidnplayr	63	.zero:
		64	ret
		65
6922	hidnplayr	66	endp
6419	hidnplayr	67
6922	hidnplayr	68	;;===========================================================================;;
9070	hidnplayr	69	proc mpint_to_big_endian uses esi edi ecx, dst, src ;////////////////////////;;
6922	hidnplayr	70	;;---------------------------------------------------------------------------;;
		71	;? Convert little endian MPINT to big endian MPINT. ;;
		72	;;---------------------------------------------------------------------------;;
9070	hidnplayr	73	;> src = pointer to little endian MPINT ;;
		74	;> dst = pointer to buffer for big endian MPINT ;;
6922	hidnplayr	75	;;---------------------------------------------------------------------------;;
		76	;< eax = MPINT number length ;;
		77	;;===========================================================================;;
		78
9070	hidnplayr	79	mov esi, [src]
		80	mov edi, [dst]
6419	hidnplayr	81	; Load length dword
		82	lodsd
		83	test eax, eax
		84	jz .zero
		85	mov ecx, eax
6922	hidnplayr	86	add esi, eax
6419	hidnplayr	87	dec esi
6922	hidnplayr	88	push eax ; we'll return length to the caller later
6419	hidnplayr	89	bswap eax
		90	stosd
		91	; Copy data, convert to big endian meanwhile
		92	std
		93	@@:
		94	lodsb
		95	mov byte[edi], al
		96	inc edi
		97	dec ecx
		98	jnz @r
		99	cld
		100	pop eax
		101	ret
		102
		103	.zero:
6922	hidnplayr	104	stosd ; Number 0 has 0 data bytes
6419	hidnplayr	105	ret
		106
		107	endp
		108
6922	hidnplayr	109	;;===========================================================================;;
		110	proc mpint_print uses ecx esi eax, src ;/////////////////////////////////////;;
		111	;;---------------------------------------------------------------------------;;
		112	;? Print MPINT to the debug board. ;;
		113	;;---------------------------------------------------------------------------;;
		114	;> src = pointer to little endian MPINT ;;
		115	;;---------------------------------------------------------------------------;;
		116	;< - ;;
		117	;;===========================================================================;;
6419	hidnplayr	118
		119	DEBUGF 1, "0x"
		120	mov esi, [src]
		121	mov ecx, [esi]
		122	test ecx, ecx
		123	jz .zero
		124	lea esi, [esi + ecx + 4 - 1]
		125	pushf
		126	std
		127	.loop:
		128	lodsb
		129	DEBUGF 1, "%x", eax:2
		130	dec ecx
		131	jnz .loop
		132	DEBUGF 1, "\n"
		133	popf
		134
		135	ret
		136
		137	.zero:
		138	DEBUGF 1, "00\n"
		139	ret
		140
		141	endp
		142
6922	hidnplayr	143	;;===========================================================================;;
9070	hidnplayr	144	proc mpint_bits uses esi ecx, dst ;//////////////////////////////////////////;;
6922	hidnplayr	145	;;---------------------------------------------------------------------------;;
9070	hidnplayr	146	;? Count the number of bits in the MPINT ;;
6922	hidnplayr	147	;;---------------------------------------------------------------------------;;
9070	hidnplayr	148	;> dst = pointer to little endian MPINT ;;
6922	hidnplayr	149	;;---------------------------------------------------------------------------;;
9070	hidnplayr	150	;< eax = highest order bit number + 1 ;;
6922	hidnplayr	151	;;===========================================================================;;
6419	hidnplayr	152
9070	hidnplayr	153	DEBUGF 1, "mpint_bits(0x%x): ", [dst]
6419	hidnplayr	154
9070	hidnplayr	155	mov esi, [dst]
		156	mov eax, [esi]
		157	test eax, eax
		158	jz .zero
		159	add esi, 4-1
		160	; Find highest order byte
		161	.byteloop:
		162	cmp byte[esi+eax], 0
		163	jne .nz
		164	dec eax
		165	jnz .byteloop
		166	.zero:
		167	DEBUGF 1, "%u\n", eax
		168	ret
		169	.nz:
		170	mov cl, byte[esi+eax]
		171	; multiply (eax - 1) by 8 to get nr of bits before this byte
		172	dec eax
		173	shl eax, 3
6922	hidnplayr	174	; Now shift bits of the highest order byte right, until the byte reaches zero, counting bits meanwhile
9070	hidnplayr	175	.bitloop:
6419	hidnplayr	176	inc eax
		177	shr cl, 1
9070	hidnplayr	178	jnz .bitloop
		179	DEBUGF 1, "%u\n", eax
6419	hidnplayr	180	ret
		181
		182	endp
		183
6922	hidnplayr	184	;;===========================================================================;;
9070	hidnplayr	185	proc mpint_bytes uses esi, dst ;/////////////////////////////////////////////;;
6922	hidnplayr	186	;;---------------------------------------------------------------------------;;
9070	hidnplayr	187	;? Count the number of bytes in the MPINT ;;
6922	hidnplayr	188	;;---------------------------------------------------------------------------;;
		189	;> dst = pointer to little endian MPINT ;;
9070	hidnplayr	190	;;---------------------------------------------------------------------------;;
		191	;< eax = highest order byte number + 1 ;;
		192	;;===========================================================================;;
		193
		194	DEBUGF 1, "mpint_bytes(0x%x): ", [dst]
		195
		196	mov esi, [dst]
		197	mov eax, [esi]
		198	test eax, eax
		199	jz .done
		200	add esi, 4-1
		201	; Find highest order byte
		202	.byteloop:
		203	cmp byte[esi+eax], 0
		204	jne .done
		205	dec eax
		206	jnz .byteloop
		207	.done:
		208	DEBUGF 1, "%u\n", eax
		209	ret
		210
		211	endp
		212
		213	;;===========================================================================;;
9090	hidnplayr	214	proc mpint_cmp uses esi edi edx ecx ebx eax, src, dst ;//////////////////////;;
9070	hidnplayr	215	;;---------------------------------------------------------------------------;;
		216	;? Compare two MPINTS. ;;
		217	;;---------------------------------------------------------------------------;;
		218	;> dst = pointer to little endian MPINT ;;
6922	hidnplayr	219	;> src = pointer to little endian MPINT ;;
		220	;;---------------------------------------------------------------------------;;
		221	;< flags are set as for single precision CMP instruction ;;
		222	;;===========================================================================;;
6419	hidnplayr	223
9070	hidnplayr	224	DEBUGF 1, "mpint_cmp(0x%x, 0x%x)\n", [dst], [src]
		225
		226	; First, check the size of both numbers
		227	stdcall mpint_bytes, [dst]
		228	mov ecx, eax
		229	stdcall mpint_bytes, [src]
		230	; If one number has more bytes, it is bigger
		231	cmp eax, ecx
		232	jne .got_answer
		233	; If both numbers have 0 bytes, they are equal
		234	test ecx, ecx
		235	jz .got_answer
		236	; Numbers have equal amount of bytes
		237	; Start comparing from the MSB towards the LSB
6419	hidnplayr	238	mov esi, [src]
		239	mov edi, [dst]
9090	hidnplayr	240	lea esi, [esi + 4 + ecx]
		241	lea edi, [edi + 4 + ecx]
9070	hidnplayr	242	; If remaining bytes is not divisible by 4, compare only one byte at a time
9090	hidnplayr	243	.loop_1:
		244	test ecx, 111b
		245	jz .done_1
6922	hidnplayr	246	dec esi
		247	dec edi
9070	hidnplayr	248	mov al, byte[esi]
		249	cmp al, byte[edi]
6922	hidnplayr	250	jne .got_answer
		251	dec ecx
9090	hidnplayr	252	jmp .loop_1
		253	; Remaining bytes is divisable by 8, compare dwords
		254	.done_1:
		255	shr ecx, 3
6922	hidnplayr	256	jz .got_answer
9090	hidnplayr	257
		258	align 8
		259	.loop_8:
		260	lea esi, [esi-8]
		261	lea edi, [edi-8]
		262	mov eax, [esi+04]
		263	mov ebx, [esi+00]
		264	cmp eax, [edi+04]
		265	jne .got_answer
		266	cmp ebx, [edi+00]
		267	jne .got_answer
		268	dec ecx
		269	jnz .loop_8
		270
6922	hidnplayr	271	.got_answer:
6419	hidnplayr	272	ret
		273
		274	endp
		275
6922	hidnplayr	276	;;===========================================================================;;
9090	hidnplayr	277	proc mpint_mov uses esi edi edx ecx ebx eax, dst, src ;//////////////////////;;
6922	hidnplayr	278	;;---------------------------------------------------------------------------;;
9070	hidnplayr	279	;? Copy MPINT. ;;
6922	hidnplayr	280	;;---------------------------------------------------------------------------;;
		281	;> dst = pointer to buffer for little endian MPINT ;;
		282	;> src = pointer to little endian MPINT ;;
		283	;;---------------------------------------------------------------------------;;
		284	;< dst = src ;;
		285	;;===========================================================================;;
6419	hidnplayr	286
9070	hidnplayr	287	DEBUGF 1, "mpint_mov(0x%x, 0x%x)\n", [dst], [src]
		288
6419	hidnplayr	289	mov esi, [src]
		290	mov edi, [dst]
9090	hidnplayr	291	mov ecx, [esi] ; Get dword count + 1
		292	add ecx, 7 ;
		293	shr ecx, 2 ;
		294	mov edx, ecx
6419	hidnplayr	295
9090	hidnplayr	296	shr ecx, 3
		297	test ecx, ecx
		298	jz .no32
		299	align 8
		300	.loop32:
		301	mov eax, [esi+00]
		302	mov ebx, [esi+04]
		303	mov [edi+00], eax
		304	mov [edi+04], ebx
		305
		306	mov eax, [esi+08]
		307	mov ebx, [esi+12]
		308	mov [edi+08], eax
		309	mov [edi+12], ebx
		310
		311	mov eax, [esi+16]
		312	mov ebx, [esi+20]
		313	mov [edi+16], eax
		314	mov [edi+20], ebx
		315
		316	mov eax, [esi+24]
		317	mov ebx, [esi+28]
		318	mov [edi+24], eax
		319	mov [edi+28], ebx
		320
		321	lea esi, [esi+32]
		322	lea edi, [edi+32]
		323	dec ecx
		324	jnz .loop32
		325	.no32:
		326
		327	test edx, 100b
		328	jz .no16
		329
		330	mov eax, [esi+00]
		331	mov ebx, [esi+04]
		332	mov [edi+00], eax
		333	mov [edi+04], ebx
		334
		335	mov eax, [esi+08]
		336	mov ebx, [esi+12]
		337	mov [edi+08], eax
		338	mov [edi+12], ebx
		339
		340	lea esi, [esi+16]
		341	lea edi, [edi+16]
		342	.no16:
		343
		344	test edx, 010b
		345	jz .no8
		346
		347	mov eax, [esi+00]
		348	mov ebx, [esi+04]
		349	mov [edi+00], eax
		350	mov [edi+04], ebx
		351
		352	lea esi, [esi+08]
		353	lea edi, [edi+08]
		354	.no8:
		355
		356	test edx, 001b
		357	jz .no4
		358
		359	mov eax, [esi+00]
		360	mov [edi+00], eax
		361	.no4:
		362
6419	hidnplayr	363	ret
		364
		365	endp
		366
6922	hidnplayr	367	;;===========================================================================;;
9090	hidnplayr	368	proc mpint_shl1 uses edi ecx, dst ;//////////////////////////////////////////;;
6922	hidnplayr	369	;;---------------------------------------------------------------------------;;
		370	;? Shift little endian MPINT one bit to the left. ;;
		371	;;---------------------------------------------------------------------------;;
		372	;> dst = pointer to little endian MPINT ;;
		373	;;---------------------------------------------------------------------------;;
		374	;< dst = dst SHL 1 ;;
		375	;;===========================================================================;;
6419	hidnplayr	376
9070	hidnplayr	377	DEBUGF 1, "mpint_shl1(0x%x)\n", [dst]
		378
9090	hidnplayr	379	mov edi, [dst]
		380	mov ecx, [edi]
		381	test ecx, 11b
		382	jnz .adjust_needed
		383	shr ecx, 2
6922	hidnplayr	384	jz .done
6419	hidnplayr	385
9090	hidnplayr	386	.length_ok:
		387	add edi, 4
		388	; Do the lowest order dword first
		389	shl dword[edi], 1
		390	lea edi, [edi+4]
6419	hidnplayr	391	dec ecx
6922	hidnplayr	392	jz .done
9090	hidnplayr	393	; And the remaining dwords
		394	.loop:
		395	rcl dword[edi], 1
		396	lea edi, [edi+4]
6922	hidnplayr	397	dec ecx
9090	hidnplayr	398	jnz .loop
6922	hidnplayr	399	.done:
9090	hidnplayr	400	jc .carry
		401	test dword[edi-4], 0x10000000
		402	jnz .add0
6419	hidnplayr	403	ret
		404
9090	hidnplayr	405	.carry:
		406	mov ecx, [dst]
		407	cmp dword[ecx], MPINT_MAX_LEN
		408	je .ovf
		409	add dword[ecx], 4
		410	mov dword[edi], 1
		411	ret
		412
		413	.add0:
		414	mov ecx, [dst]
		415	cmp dword[ecx], MPINT_MAX_LEN
		416	je .ovf
		417	add dword[ecx], 4
		418	mov dword[edi], 0
		419	ret
		420
		421	.ovf:
		422	int3
		423	;;;;
		424	ret
		425
		426	.adjust_needed:
		427	add ecx, 3
		428	and ecx, not 3
		429	stdcall mpint_grow, edi, ecx
		430	jmp .length_ok
		431
6419	hidnplayr	432	endp
		433
6922	hidnplayr	434	;;===========================================================================;;
		435	proc mpint_shr1 uses edi ecx, dst ;//////////////////////////////////////////;;
		436	;;---------------------------------------------------------------------------;;
		437	;? Shift little endian MPINT one bit to the right. ;;
		438	;;---------------------------------------------------------------------------;;
		439	;> dst = pointer to little endian MPINT ;;
		440	;;---------------------------------------------------------------------------;;
		441	;< dst = dst SHR 1 ;;
		442	;;===========================================================================;;
6419	hidnplayr	443
9070	hidnplayr	444	DEBUGF 1, "mpint_shr1(0x%x)\n", [dst]
		445
6419	hidnplayr	446	mov edi, [dst]
6922	hidnplayr	447	mov ecx, [edi]
9090	hidnplayr	448	test ecx, 11b
		449	jnz .adjust_needed
		450
		451	.length_ok:
		452	shr ecx, 2
6922	hidnplayr	453	jz .done
9090	hidnplayr	454	lea edi, [edi+ecx*4]
		455	; Do the highest order dword first
		456	shr dword[edi], 1
		457	lea edi, [edi-4]
6922	hidnplayr	458	dec ecx
		459	jz .done
9090	hidnplayr	460	; And the remaining dwords
		461	.loop:
		462	rcr dword[edi], 1
		463	lea edi, [edi-4]
		464	dec ecx
		465	jnz .loop
6922	hidnplayr	466	.done:
6419	hidnplayr	467	ret
		468
9090	hidnplayr	469	.adjust_needed:
		470	add ecx, 3
		471	and ecx, not 3
		472	stdcall mpint_grow, edi, ecx
		473	jmp .length_ok
		474
6419	hidnplayr	475	endp
		476
6922	hidnplayr	477	;;===========================================================================;;
		478	proc mpint_shl uses eax ebx ecx edx esi edi, dst, shift ;////////////////////;;
		479	;;---------------------------------------------------------------------------;;
		480	;? Left shift little endian MPINT by x bits. ;;
		481	;;---------------------------------------------------------------------------;;
		482	;> dst = pointer to little endian MPINT ;;
		483	;> shift = number of bits to shift the MPINT ;;
		484	;;---------------------------------------------------------------------------;;
		485	;< - ;;
		486	;;===========================================================================;;
6419	hidnplayr	487
9070	hidnplayr	488	DEBUGF 1, "mpint_shl(0x%x, %u)\n", [dst], [shift]
		489
		490	; Calculate new size
		491	stdcall mpint_bits, [dst]
		492	add eax, [shift]
		493	shr eax, 3
		494	cmp eax, MPINT_MAX_LEN
		495	jae .overflow ;;
		496	inc eax
		497	mov esi, [dst]
		498	mov [esi], eax
		499
6419	hidnplayr	500	mov ecx, [shift]
		501	shr ecx, 3 ; 8 bits in one byte
		502	add esi, MPINT_MAX_LEN+4-4
		503	mov edi, esi
		504	and ecx, not 11b
		505	sub esi, ecx
		506	mov edx, MPINT_MAX_LEN/4-1
		507	shr ecx, 2 ; 4 bytes in one dword
		508	push ecx
		509	sub edx, ecx
		510	mov ecx, [shift]
		511	and ecx, 11111b
		512	std
		513	.loop:
		514	lodsd
		515	mov ebx, [esi]
		516	shld eax, ebx, cl
		517	stosd
		518	dec edx
		519	jnz .loop
		520	lodsd
		521	shl eax, cl
		522	stosd
		523
9070	hidnplayr	524	; fill the LSBs with zeros
6419	hidnplayr	525	pop ecx
		526	test ecx, ecx
		527	jz @f
		528	xor eax, eax
		529	rep stosd
		530	@@:
		531	cld
		532	ret
		533
		534	.zero:
6922	hidnplayr	535	mov eax, [dst]
		536	mov dword[eax], 0
6419	hidnplayr	537	ret
		538
9070	hidnplayr	539	.overflow:
		540	int3
		541	ret
		542
6419	hidnplayr	543	endp
		544
6922	hidnplayr	545	;;===========================================================================;;
		546	proc mpint_shlmov uses eax ebx ecx edx esi edi, dst, src, shift ;////////////;;
		547	;;---------------------------------------------------------------------------;;
		548	;? Left shift by x bits and copy little endian MPINT. ;;
		549	;;---------------------------------------------------------------------------;;
		550	;> src = pointer to little endian MPINT ;;
		551	;> dst = pointer to little endian MPINT ;;
		552	;> shift = number of bits to shift the MPINT to the left ;;
		553	;;---------------------------------------------------------------------------;;
		554	;< dst = src SHL shift ;;
		555	;;===========================================================================;;
6419	hidnplayr	556
9070	hidnplayr	557	DEBUGF 1, "mpint_shlmov(0x%x, 0x%x, %u)\n", [dst], [src], [shift]
		558
		559	stdcall mpint_bits, [src]
		560	test eax, eax
		561	jz .zero
		562	add eax, [shift]
		563	shr eax, 3
		564	inc eax
		565	mov edi, [dst]
		566	mov [edi], eax
		567
		568	cmp eax, MPINT_MAX_LEN
9090	hidnplayr	569	jae .overflow
9070	hidnplayr	570
6419	hidnplayr	571	mov esi, [src]
		572	add esi, MPINT_MAX_LEN+4-4
		573	add edi, MPINT_MAX_LEN+4-4
9070	hidnplayr	574	mov ecx, [shift]
		575	shr ecx, 3 ; 8 bits in one byte
6419	hidnplayr	576	and ecx, not 11b
		577	sub esi, ecx
		578	mov edx, MPINT_MAX_LEN/4-1
		579	shr ecx, 2 ; 4 bytes in one dword
		580	push ecx
		581	sub edx, ecx
		582	mov ecx, [shift]
		583	and ecx, 11111b
		584	std
		585	.loop:
		586	lodsd
		587	mov ebx, [esi]
		588	shld eax, ebx, cl
		589	stosd
		590	dec edx
		591	jnz .loop
		592	lodsd
		593	shl eax, cl
		594	stosd
		595
		596	; fill the lsb bytes with zeros
		597	pop ecx
		598	test ecx, ecx
		599	jz @f
		600	xor eax, eax
		601	rep stosd
		602	@@:
		603	cld
		604	ret
		605
		606	.zero:
6922	hidnplayr	607	mov eax, [dst]
		608	mov dword[eax], 0
6419	hidnplayr	609	ret
		610
9070	hidnplayr	611	.overflow:
		612	int3
		613	ret
		614
6419	hidnplayr	615	endp
		616
6922	hidnplayr	617	;;===========================================================================;;
9090	hidnplayr	618	proc mpint_add uses esi edi edx ecx ebx eax, dst, src ;//////////////////////;;
6922	hidnplayr	619	;;---------------------------------------------------------------------------;;
		620	;? Add a little endian MPINT to another little endian MPINT. ;;
		621	;;---------------------------------------------------------------------------;;
		622	;> src = pointer to little endian MPINT ;;
		623	;> dst = pointer to little endian MPINT ;;
		624	;;---------------------------------------------------------------------------;;
		625	;< dst = dst + src ;;
		626	;;===========================================================================;;
6419	hidnplayr	627
9090	hidnplayr	628	locals
		629	dd_cnt dd ?
		630	endl
		631
9070	hidnplayr	632	DEBUGF 1, "mpint_add(0x%x, 0x%x)\n", [dst], [src]
		633
9090	hidnplayr	634	; Grow both numbers to same 4-byte boundary, if not already the case
6419	hidnplayr	635	mov esi, [src]
		636	mov edi, [dst]
9090	hidnplayr	637	mov ecx, [esi]
		638	test ecx, 11b
		639	jnz .adjust_needed
		640	cmp ecx, [edi]
		641	jne .adjust_needed
9070	hidnplayr	642
9090	hidnplayr	643	; Do the additions
6922	hidnplayr	644	.length_ok:
		645	add esi, 4
6419	hidnplayr	646	add edi, 4
9090	hidnplayr	647	shr ecx, 2
6922	hidnplayr	648	jz .done
9090	hidnplayr	649	mov eax, ecx
		650	and eax, 111b
		651	mov [dd_cnt], eax
		652	shr ecx, 3
		653	test ecx, ecx ; Clear carry flag
		654	jz .no32
		655
		656	.loop32:
		657	mov eax, [esi+00]
		658	mov edx, [esi+04]
		659	adc [edi+00], eax
		660	adc [edi+04], edx
		661
		662	mov eax, [esi+08]
		663	mov edx, [esi+12]
		664	adc [edi+08], eax
		665	adc [edi+12], edx
		666
		667	mov eax, [esi+16]
		668	mov edx, [esi+20]
		669	adc [edi+16], eax
		670	adc [edi+20], edx
		671
		672	mov eax, [esi+24]
		673	mov edx, [esi+28]
		674	adc [edi+24], eax
		675	adc [edi+28], edx
		676
		677	lea esi, [esi + 32]
		678	lea edi, [edi + 32]
6922	hidnplayr	679	dec ecx
9090	hidnplayr	680	jnz .loop32
		681
		682	.no32:
		683	mov ecx, [dd_cnt]
		684	dec ecx
		685	js .check_ovf
		686	inc ecx
		687	.dword_loop:
		688	mov eax, [esi+0]
		689	adc [edi+0], eax
		690	lea esi, [esi + 4]
		691	lea edi, [edi + 4]
		692	dec ecx
		693	jnz .dword_loop
		694
		695	.check_ovf:
		696	jc .add_1 ; Carry
		697	test byte[edi-1], 0x80
		698	jnz .add_0 ; Currently highest bit set
6922	hidnplayr	699	.done:
9090	hidnplayr	700	ret
9070	hidnplayr	701
9090	hidnplayr	702	; Highest bit was set, add a 0 byte as MSB if possible
		703	.add_0:
		704	mov ecx, [dst]
		705	cmp dword[ecx], MPINT_MAX_LEN
		706	jae .ovf_0
		707	mov byte[edi], 0
		708	inc dword[ecx]
		709	ret
6419	hidnplayr	710
9090	hidnplayr	711	.ovf_0:
		712	int3
		713	clc
		714	; TODO: set overflow flag?
6419	hidnplayr	715	ret
		716
9090	hidnplayr	717	; Carry bit was set, add a 1 byte as MSB if possible
		718	.add_1:
		719	mov ecx, [dst]
		720	cmp dword[ecx], MPINT_MAX_LEN
		721	jae .ovf_1
		722	mov byte[edi], 1
		723	inc dword[ecx]
6922	hidnplayr	724	ret
		725
9090	hidnplayr	726	.ovf_1:
		727	int3
		728	stc
		729	; TODO: set overflow flag?
6922	hidnplayr	730	ret
		731
9090	hidnplayr	732	.adjust_needed:
		733	; mov ecx, [esi]
		734	mov eax, [edi]
		735	; find the maximum of the two in ecx
		736	mov edx, ecx
		737	sub edx, eax
		738	sbb ebx, ebx
		739	and ebx, edx
		740	sub ecx, ebx
		741	; align to 4 byte boundary
		742	add ecx, 3
		743	and ecx, not 3
		744	; adjust both mpints
		745	stdcall mpint_grow, esi, ecx
9070	hidnplayr	746	stdcall mpint_grow, edi, ecx
		747	jmp .length_ok
		748
6419	hidnplayr	749	endp
		750
6922	hidnplayr	751	;;===========================================================================;;
9090	hidnplayr	752	proc mpint_sub uses esi edi edx ecx ebx eax, dst, src ;//////////////////////;;
6922	hidnplayr	753	;;---------------------------------------------------------------------------;;
		754	;? Subtract a little endian MPINT to another little endian MPINT. ;;
		755	;;---------------------------------------------------------------------------;;
		756	;> src = pointer to little endian MPINT ;;
		757	;> dst = pointer to little endian MPINT ;;
		758	;;---------------------------------------------------------------------------;;
		759	;< dst = dst - src ;;
		760	;;===========================================================================;;
6419	hidnplayr	761
9090	hidnplayr	762	locals
		763	dd_cnt dd ?
		764	endl
		765
9070	hidnplayr	766	DEBUGF 1, "mpint_sub(0x%x, 0x%x)\n", [dst], [src]
		767
9090	hidnplayr	768	; Grow both numbers to same 4-byte boundary, if not already the case
6419	hidnplayr	769	mov esi, [src]
6922	hidnplayr	770	mov edi, [dst]
9090	hidnplayr	771	mov ecx, [esi]
		772	test ecx, 11b
		773	jnz .adjust_needed
		774	cmp ecx, [edi]
		775	jne .adjust_needed
6922	hidnplayr	776
9090	hidnplayr	777	; Do the subtractions
9070	hidnplayr	778	.length_ok:
6419	hidnplayr	779	add esi, 4
		780	add edi, 4
9090	hidnplayr	781	shr ecx, 2
6922	hidnplayr	782	jz .done
9090	hidnplayr	783	mov eax, ecx
		784	and eax, 111b
		785	mov [dd_cnt], eax
		786	shr ecx, 3
		787	test ecx, ecx ; Clear carry flag
		788	jz .no32
		789
		790	.loop32:
		791	mov eax, [esi+00]
		792	mov edx, [esi+04]
		793	sbb [edi+00], eax
		794	sbb [edi+04], edx
		795
		796	mov eax, [esi+08]
		797	mov edx, [esi+12]
		798	sbb [edi+08], eax
		799	sbb [edi+12], edx
		800
		801	mov eax, [esi+16]
		802	mov edx, [esi+20]
		803	sbb [edi+16], eax
		804	sbb [edi+20], edx
		805
		806	mov eax, [esi+24]
		807	mov edx, [esi+28]
		808	sbb [edi+24], eax
		809	sbb [edi+28], edx
		810
		811	lea esi, [esi + 32]
		812	lea edi, [edi + 32]
6419	hidnplayr	813	dec ecx
9090	hidnplayr	814	jnz .loop32
		815
		816	.no32:
		817	mov ecx, [dd_cnt]
		818	dec ecx
		819	js .done
		820	inc ecx
		821	.dword_loop:
		822	mov eax, [esi+0]
		823	sbb [edi+0], eax
		824	lea esi, [esi + 4]
		825	lea edi, [edi + 4]
		826	dec ecx
		827	jnz .dword_loop
		828
6922	hidnplayr	829	.done:
6419	hidnplayr	830	ret
		831
9090	hidnplayr	832	.adjust_needed:
		833	; mov ecx, [esi]
		834	mov eax, [edi]
		835	; find the maximum of the two in ecx
		836	mov edx, ecx
		837	sub edx, eax
		838	sbb ebx, ebx
		839	and ebx, edx
		840	sub ecx, ebx
		841	; align to 4 byte boundary
		842	add ecx, 3
		843	and ecx, not 3
		844	; adjust both mpints
		845	stdcall mpint_grow, esi, ecx
9070	hidnplayr	846	stdcall mpint_grow, edi, ecx
		847	jmp .length_ok
		848
6419	hidnplayr	849	endp
		850
		851
6922	hidnplayr	852	;;===========================================================================;;
9070	hidnplayr	853	proc mpint_shrink uses eax edi, dst ;////////////////////////////////////////;;
6922	hidnplayr	854	;;---------------------------------------------------------------------------;;
9070	hidnplayr	855	;? Get rid of unnescessary leading zeroes on a little endian MPINT. ;;
6922	hidnplayr	856	;;---------------------------------------------------------------------------;;
		857	;> src = pointer to little endian MPINT ;;
		858	;;---------------------------------------------------------------------------;;
		859	;< ;;
		860	;;===========================================================================;;
6419	hidnplayr	861
9070	hidnplayr	862	DEBUGF 1, "mpint_shrink(0x%x)\n", [dst]
		863
		864	stdcall mpint_bits, [dst]
		865	shr eax, 3
		866	inc eax
6922	hidnplayr	867	mov edi, [dst]
9070	hidnplayr	868	mov [edi], eax
		869
		870	ret
		871
		872	endp
		873
		874	;;===========================================================================;;
		875	proc mpint_grow uses eax edi ecx, dst, length ;//////////////////////////////;;
		876	;;---------------------------------------------------------------------------;;
		877	;? Add leading zeroes on a little endian MPINT. ;;
		878	;;---------------------------------------------------------------------------;;
		879	;> src = pointer to little endian MPINT ;;
		880	;> length = total length of the new MPINT in bytes ;;
		881	;;---------------------------------------------------------------------------;;
		882	;< ;;
		883	;;===========================================================================;;
		884
		885	DEBUGF 1, "mpint_grow(0x%x, %u): ", [dst], [length]
		886
		887	mov edi, [dst]
		888	mov eax, [edi]
		889	mov ecx, [length]
		890	sub ecx, eax
		891	jbe .dontgrow
		892	lea edi, [edi + 4 + eax]
6419	hidnplayr	893	xor al, al
9070	hidnplayr	894	rep stosb
		895	mov eax, [length]
6922	hidnplayr	896	mov edi, [dst]
9070	hidnplayr	897	mov [edi], eax
		898	DEBUGF 1, "ok\n"
		899	ret
6922	hidnplayr	900
9070	hidnplayr	901	.dontgrow:
		902	DEBUGF 1, "already large enough!\n"
6922	hidnplayr	903	ret
		904
		905	endp
		906
		907	;;===========================================================================;;
9985	hidnplayr	908	proc mpint_mul uses eax ebx ecx edx esi edi, dst, a, b ;/////////////////////;;
6922	hidnplayr	909	;;---------------------------------------------------------------------------;;
9090	hidnplayr	910	;? Multiply a little endian MPINT with another little endian MPINT and store ;;
		911	;? in a third one. ;;
6922	hidnplayr	912	;;---------------------------------------------------------------------------;;
9090	hidnplayr	913	;> dst = pointer to little endian MPINT ;;
		914	;> a = pointer to little endian MPINT ;;
		915	;> b = pointer to little endian MPINT ;;
6922	hidnplayr	916	;;---------------------------------------------------------------------------;;
9090	hidnplayr	917	;< dst = a * b ;;
6922	hidnplayr	918	;;===========================================================================;;
		919
9090	hidnplayr	920	locals
		921	asize dd ?
		922	bsize dd ?
		923	counter dd ?
		924	esp_ dd ?
		925	endl
9070	hidnplayr	926
9090	hidnplayr	927	DEBUGF 1, "mpint_mul(0x%x, 0x%x, 0x%x)\n", [dst], [a], [b]
		928
		929	; Grow both numbers to individual 4-byte boundary, if not already the case
		930	mov esi, [a]
		931	mov edx, [b]
		932	mov ecx, [esi]
		933	mov ebx, [edx]
		934	test ecx, 11b
		935	jnz .adjust_needed
		936	test ebx, 11b
		937	jnz .adjust_needed
		938	.length_ok:
		939
9985	hidnplayr	940	; Must have a size >= b size.
9090	hidnplayr	941	cmp ebx, ecx
		942	ja .swap_a_b
		943	.conditions_ok:
		944
9985	hidnplayr	945	; dst size will be a size + b size
9090	hidnplayr	946	lea eax, [ebx + ecx]
		947	cmp eax, MPINT_MAX_LEN
		948	ja .ovf
		949
9985	hidnplayr	950	; [asize] = number of dwords in a
9090	hidnplayr	951	shr ecx, 2
		952	jz .zero
		953	mov [asize], ecx
		954	; esi = x ptr
		955	add esi, 4
		956
9985	hidnplayr	957	; [bsize] = number of dwords in b
9090	hidnplayr	958	shr ebx, 2
		959	jz .zero
		960	mov [bsize], ebx
9985	hidnplayr	961	; edx = b ptr (temporarily)
9090	hidnplayr	962	add edx, 4
		963
9985	hidnplayr	964	; store dst size
9090	hidnplayr	965	mov edi, [dst]
		966	mov [edi], eax
9985	hidnplayr	967	; edi = dst ptr
9090	hidnplayr	968	add edi, 4
		969
		970	; Use esp as frame pointer instead of ebp
		971	; ! Use the stack with extreme caution from here on !
		972	mov [esp_], esp
		973	mov esp, ebp
		974
9985	hidnplayr	975	; ebp = b ptr
9090	hidnplayr	976	mov ebp, edx
		977
		978	; Do the first multiplication
9985	hidnplayr	979	mov eax, [esi] ; load a[0]
		980	mul dword[ebp] ; multiply by b[0]
		981	mov [edi], eax ; store to dest[0]
		982	; mov ecx, [asize] ; asize
		983	dec ecx ; if asize = 1, bsize = 1 too
9090	hidnplayr	984	jz .done
		985
		986	; Prepare to enter loop1
		987	mov eax, [asize-ebp+esp]
		988
		989	mov ebx, edx
9985	hidnplayr	990	lea esi, [esi + eax * 4] ; make a ptr point at end
		991	lea edi, [edi + eax * 4] ; offset dst ptr by asize
9090	hidnplayr	992	neg ecx ; negate j size/index for inner loop
		993	xor eax, eax ; clear carry
		994
		995	align 8
		996	.loop1:
		997	adc ebx, 0
9985	hidnplayr	998	mov eax, [esi + ecx * 4] ; load next dword at a[j]
9090	hidnplayr	999	mul dword[ebp]
		1000	add eax, ebx
		1001	mov [edi + ecx * 4], eax
		1002	inc ecx
		1003	mov ebx, edx
		1004	jnz .loop1
		1005
		1006	adc ebx, 0
		1007	mov eax, [bsize-ebp+esp]
		1008	mov [edi], ebx ; most significant dword of the product
		1009	add edi, 4 ; increment dst
		1010	dec eax
		1011	jz .skip
9985	hidnplayr	1012	mov [counter-ebp+esp], eax ; set index i to bsize
9090	hidnplayr	1013
		1014	.outer:
9985	hidnplayr	1015	add ebp, 4 ; make ebp point to next b dword
9090	hidnplayr	1016	mov ecx, [asize-ebp+esp]
		1017	neg ecx
		1018	xor ebx, ebx
		1019
		1020	.loop2:
		1021	adc ebx, 0
		1022	mov eax, [esi + ecx * 4]
		1023	mul dword[ebp]
		1024	add eax, ebx
		1025	mov ebx, [edi + ecx * 4]
		1026	adc edx, 0
		1027	add ebx, eax
		1028	mov [edi + ecx * 4], ebx
		1029	inc ecx
		1030	mov ebx, edx
		1031	jnz .loop2
		1032
		1033	adc ebx, 0
		1034
		1035	mov [edi], ebx
		1036	add edi, 4
		1037	mov eax, [counter-ebp+esp]
		1038	dec eax
		1039	mov [counter-ebp+esp], eax
		1040	jnz .outer
		1041
		1042	.skip:
		1043	; restore esp, ebp
		1044	mov ebp, esp
		1045	mov esp, [esp_]
		1046
		1047	ret
		1048
		1049	.done:
9985	hidnplayr	1050	mov [edi+4], edx ; store to dst[1]
9090	hidnplayr	1051	; restore esp, ebp
		1052	mov ebp, esp
		1053	mov esp, [esp_]
		1054
		1055	ret
		1056
		1057	.ovf:
		1058	int3
		1059
		1060	.zero:
6922	hidnplayr	1061	mov eax, [dst]
		1062	mov dword[eax], 0
		1063
6419	hidnplayr	1064	ret
		1065
9090	hidnplayr	1066	.adjust_needed:
		1067	; align to 4 byte boundary
		1068	add ecx, 3
		1069	and ecx, not 3
		1070	add ebx, 3
		1071	and ebx, not 3
		1072	; adjust both mpints
		1073	stdcall mpint_grow, esi, ecx
		1074	stdcall mpint_grow, edx, ebx
		1075	jmp .length_ok
		1076
		1077	.swap_a_b:
		1078	mov eax, esi
		1079	mov esi, edx
		1080	mov edx, eax
		1081
		1082	mov eax, ebx
		1083	mov ebx, ecx
		1084	mov ecx, eax
		1085	jmp .conditions_ok
		1086
6419	hidnplayr	1087	endp
		1088
6922	hidnplayr	1089	;;===========================================================================;;
9090	hidnplayr	1090	proc mpint_mod uses eax ebx ecx, dst, m ;////////////////////////////////////;;
6922	hidnplayr	1091	;;---------------------------------------------------------------------------;;
		1092	;? Find the modulo (remainder after division) of dst by mod. ;;
		1093	;;---------------------------------------------------------------------------;;
		1094	;> dst = pointer to little endian MPINT ;;
		1095	;> mod = pointer to little endian MPINT ;;
		1096	;;---------------------------------------------------------------------------;;
9090	hidnplayr	1097	;< dst = dst MOD m ;;
6922	hidnplayr	1098	;;===========================================================================;;
6419	hidnplayr	1099
6922	hidnplayr	1100	locals
		1101	mpint_tmp rb MPINT_MAX_LEN+4
		1102	endl
		1103
9090	hidnplayr	1104	DEBUGF 1, "mpint_mod(0x%x, 0x%x)\n", [dst], [m]
		1105
		1106	stdcall mpint_cmp, [m], [dst]
		1107	ja .done ; if mod > dst, dst = dst
9070	hidnplayr	1108	je .zero ; if mod == dst, dst = 0
6419	hidnplayr	1109
9070	hidnplayr	1110	; left shift mod until the high order bits of mod and dst are aligned
6419	hidnplayr	1111
9070	hidnplayr	1112	stdcall mpint_bits, [dst]
6419	hidnplayr	1113	mov ecx, eax
9090	hidnplayr	1114	stdcall mpint_bits, [m]
9070	hidnplayr	1115	test eax, eax
		1116	jz .zero ; if mod is zero, return
6419	hidnplayr	1117	sub ecx, eax
9070	hidnplayr	1118	lea ebx, [mpint_tmp]
9090	hidnplayr	1119	stdcall mpint_shlmov, ebx, [m], ecx
6419	hidnplayr	1120	inc ecx
		1121
		1122	; For every bit in dst (starting from the high order bit):
9070	hidnplayr	1123	.bitloop:
		1124	stdcall mpint_cmp, [dst], ebx ; If dst > mpint_tmp
9090	hidnplayr	1125	jb @f
9070	hidnplayr	1126	stdcall mpint_sub, [dst], ebx ; dst = dst - mpint_tmp
6419	hidnplayr	1127	@@:
		1128	dec ecx
		1129	jz .done
		1130
9070	hidnplayr	1131	stdcall mpint_shr1, ebx ; mpint = mpint >> 1
		1132	jmp .bitloop
		1133
6419	hidnplayr	1134	.done:
9090	hidnplayr	1135	; adjust size of dst so it is no larger than mod
		1136	mov ebx, [dst]
		1137	mov ecx, [ebx] ; current size
		1138	mov eax, [m]
		1139	mov eax, [eax] ; size of mod
		1140	cmp ecx, eax
		1141	jb .ret
		1142	mov [ebx], eax
		1143	.ret:
6419	hidnplayr	1144	ret
		1145
9090	hidnplayr	1146	.zero:
		1147	mov ebx, [dst]
		1148	mov dword[ebx], 0
		1149	ret
		1150
6419	hidnplayr	1151	endp
		1152
6922	hidnplayr	1153	;;===========================================================================;;
9985	hidnplayr	1154	proc mpint_modexp uses edi eax ebx ecx edx, dest, b, e, m ;//////////////////;;
6922	hidnplayr	1155	;;---------------------------------------------------------------------------;;
		1156	;? Find the modulo (remainder after division) of dst by mod. ;;
		1157	;;---------------------------------------------------------------------------;;
		1158	;> dst = pointer to buffer for little endian MPINT ;;
		1159	;> base = pointer to little endian MPINT ;;
		1160	;> exp = pointer to little endian MPINT ;;
		1161	;> mod = pointer to little endian MPINT ;;
		1162	;;---------------------------------------------------------------------------;;
9090	hidnplayr	1163	;< dst = b ** e MOD m ;;
6922	hidnplayr	1164	;;===========================================================================;;
6419	hidnplayr	1165
6922	hidnplayr	1166	locals
9985	hidnplayr	1167	dst1 dd ?
		1168	dst2 dd ?
		1169	tmp rb MPINT_MAX_LEN+4
6922	hidnplayr	1170	endl
		1171
9985	hidnplayr	1172	DEBUGF 1, "mpint_modexp(0x%x, 0x%x, 0x%x, 0x%x)\n", [dest], [b], [e], [m]
9090	hidnplayr	1173
6419	hidnplayr	1174	; If mod is zero, return
9090	hidnplayr	1175	stdcall mpint_bytes, [m]
9070	hidnplayr	1176	test eax, eax
		1177	jz .mod_zero
9090	hidnplayr	1178	test eax, 3
		1179	jnz .grow_mod
		1180	.modsize_ok:
6419	hidnplayr	1181
9070	hidnplayr	1182	; Find highest order byte in exponent
9090	hidnplayr	1183	stdcall mpint_bytes, [e]
9070	hidnplayr	1184	test eax, eax
		1185	jz .exp_zero
		1186	mov ecx, eax
9090	hidnplayr	1187	mov edi, [e]
6419	hidnplayr	1188	lea edi, [edi + 4 + ecx - 1]
9070	hidnplayr	1189
9985	hidnplayr	1190	; Set up temp variables
		1191	lea eax, [tmp]
		1192	mov edx, [dest]
		1193	mov [dst1], eax
		1194	mov [dst2], edx
		1195
6419	hidnplayr	1196	; Find the highest order bit in this byte
		1197	mov al, [edi]
		1198	test al, al
		1199	jz .invalid
		1200	mov bl, 9
		1201	@@:
		1202	dec bl
		1203	shl al, 1
		1204	jnc @r
		1205
		1206	; Initialise result to base, to take care of the highest order bit
9985	hidnplayr	1207	stdcall mpint_mov, [dst1], [b]
6419	hidnplayr	1208	dec bl
		1209	jz .next_byte
		1210	.bit_loop:
		1211	; For each bit, square result
9985	hidnplayr	1212	stdcall mpint_mul, [dst2], [dst1], [dst1]
		1213	stdcall mpint_mod, [dst2], [m]
6419	hidnplayr	1214
		1215	; If the bit is set, multiply result by the base
		1216	shl al, 1
9985	hidnplayr	1217	jnc .bit_zero
		1218	stdcall mpint_mul, [dst1], [b], [dst2]
		1219	stdcall mpint_mod, [dst1], [m]
6419	hidnplayr	1220	dec bl
		1221	jnz .bit_loop
9985	hidnplayr	1222	jmp .next_byte
		1223
		1224	.bit_zero:
		1225	mov edx, [dst1]
		1226	mov esi, [dst2]
		1227	mov [dst2], edx
		1228	mov [dst1], esi
		1229	dec bl
		1230	jnz .bit_loop
		1231
6419	hidnplayr	1232	.next_byte:
		1233	dec ecx
		1234	jz .done
		1235	dec edi
		1236	mov al, [edi]
		1237	mov bl, 8
		1238	jmp .bit_loop
		1239	.done:
9985	hidnplayr	1240	mov edx, [dest]
		1241	cmp edx, [dst1]
		1242	je @f
		1243	stdcall mpint_mov, [dest], [dst1]
		1244	@@:
		1245
6419	hidnplayr	1246	ret
		1247
		1248	.mod_zero:
6469	hidnplayr	1249	DEBUGF 3, "modexp with modulo 0\n"
6419	hidnplayr	1250	; if mod is zero, result = 0
9985	hidnplayr	1251	mov eax, [dest]
6922	hidnplayr	1252	mov dword[eax], 0
6419	hidnplayr	1253	ret
		1254
		1255	.exp_zero:
6469	hidnplayr	1256	DEBUGF 3, "modexp with exponent 0\n"
6419	hidnplayr	1257	; if exponent is zero, result = 1
9985	hidnplayr	1258	mov eax, [dest]
6922	hidnplayr	1259	mov dword[eax], 1
6419	hidnplayr	1260	mov byte[eax+4], 1
		1261	ret
		1262
		1263	.invalid:
6469	hidnplayr	1264	DEBUGF 3, "modexp: Invalid input!\n"
6419	hidnplayr	1265	ret
		1266
9090	hidnplayr	1267	.grow_mod:
		1268	add eax, 3
		1269	and eax, not 3
		1270	stdcall mpint_grow, [m], eax
		1271	jmp .modsize_ok
		1272
		1273	endp
		1274

Subversion Repositories Kolibri OS

(root)/programs/network/ssh/mpint.inc – Rev 9985