Rev 9090 | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 9090 | Rev 9985 | ||
---|---|---|---|
Line 1... | Line 1... | ||
1 | ; mpint.inc - Multi precision integer procedures |
1 | ; mpint.inc - Multi precision integer procedures |
2 | ; |
2 | ; |
3 | ; Copyright (C) 2015-2021 Jeffrey Amelynck |
3 | ; Copyright (C) 2015-2024 Jeffrey Amelynck |
4 | ; |
4 | ; |
5 | ; This program is free software: you can redistribute it and/or modify |
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 |
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 |
7 | ; the Free Software Foundation, either version 3 of the License, or |
8 | ; (at your option) any later version. |
8 | ; (at your option) any later version. |
Line 903... | Line 903... | ||
903 | ret |
903 | ret |
Line 904... | Line 904... | ||
904 | 904 | ||
Line 905... | Line 905... | ||
905 | endp |
905 | endp |
906 | 906 | ||
907 | ;;===========================================================================;; |
907 | ;;===========================================================================;; |
908 | proc mpint_mul uses eax ebx ecx edx esi edi, dst, a, b ;///////////////////////;; |
908 | proc mpint_mul uses eax ebx ecx edx esi edi, dst, a, b ;/////////////////////;; |
909 | ;;---------------------------------------------------------------------------;; |
909 | ;;---------------------------------------------------------------------------;; |
910 | ;? Multiply a little endian MPINT with another little endian MPINT and store ;; |
910 | ;? Multiply a little endian MPINT with another little endian MPINT and store ;; |
911 | ;? in a third one. ;; |
911 | ;? in a third one. ;; |
Line 935... | Line 935... | ||
935 | jnz .adjust_needed |
935 | jnz .adjust_needed |
936 | test ebx, 11b |
936 | test ebx, 11b |
937 | jnz .adjust_needed |
937 | jnz .adjust_needed |
938 | .length_ok: |
938 | .length_ok: |
Line 939... | Line 939... | ||
939 | 939 | ||
940 | ; Must have Asize >= Bsize. |
940 | ; Must have a size >= b size. |
941 | cmp ebx, ecx |
941 | cmp ebx, ecx |
942 | ja .swap_a_b |
942 | ja .swap_a_b |
Line 943... | Line 943... | ||
943 | .conditions_ok: |
943 | .conditions_ok: |
944 | 944 | ||
945 | ; D size will be A size + B size |
945 | ; dst size will be a size + b size |
946 | lea eax, [ebx + ecx] |
946 | lea eax, [ebx + ecx] |
Line 947... | Line 947... | ||
947 | cmp eax, MPINT_MAX_LEN |
947 | cmp eax, MPINT_MAX_LEN |
948 | ja .ovf |
948 | ja .ovf |
949 | 949 | ||
950 | ; [Asize] = number of dwords in x |
950 | ; [asize] = number of dwords in a |
951 | shr ecx, 2 |
951 | shr ecx, 2 |
952 | jz .zero |
952 | jz .zero |
Line 953... | Line 953... | ||
953 | mov [asize], ecx |
953 | mov [asize], ecx |
954 | ; esi = x ptr |
954 | ; esi = x ptr |
955 | add esi, 4 |
955 | add esi, 4 |
956 | 956 | ||
957 | ; [Bsize] = number of dwords in y |
957 | ; [bsize] = number of dwords in b |
958 | shr ebx, 2 |
958 | shr ebx, 2 |
Line 959... | Line 959... | ||
959 | jz .zero |
959 | jz .zero |
960 | mov [bsize], ebx |
960 | mov [bsize], ebx |
961 | ; edx = y ptr (temporarily) |
961 | ; edx = b ptr (temporarily) |
962 | add edx, 4 |
962 | add edx, 4 |
963 | 963 | ||
Line 964... | Line 964... | ||
964 | ; store D size |
964 | ; store dst size |
965 | mov edi, [dst] |
965 | mov edi, [dst] |
966 | mov [edi], eax |
966 | mov [edi], eax |
967 | ; edi = D ptr |
967 | ; edi = dst ptr |
Line 968... | Line 968... | ||
968 | add edi, 4 |
968 | add edi, 4 |
969 | 969 | ||
Line 970... | Line 970... | ||
970 | ; Use esp as frame pointer instead of ebp |
970 | ; Use esp as frame pointer instead of ebp |
971 | ; ! Use the stack with extreme caution from here on ! |
971 | ; ! Use the stack with extreme caution from here on ! |
972 | mov [esp_], esp |
972 | mov [esp_], esp |
973 | mov esp, ebp |
973 | mov esp, ebp |
974 | 974 | ||
975 | ; ebp = B ptr |
975 | ; ebp = b ptr |
976 | mov ebp, edx |
976 | mov ebp, edx |
Line 977... | Line 977... | ||
977 | 977 | ||
978 | ; Do the first multiplication |
978 | ; Do the first multiplication |
Line 979... | Line 979... | ||
979 | mov eax, [esi] ; load A[0] |
979 | mov eax, [esi] ; load a[0] |
980 | mul dword[ebp] ; multiply by B[0] |
980 | mul dword[ebp] ; multiply by b[0] |
981 | mov [edi], eax ; store to D[0] |
981 | mov [edi], eax ; store to dest[0] |
982 | ; mov ecx, [Asize] ; Asize |
982 | ; mov ecx, [asize] ; asize |
983 | dec ecx ; if Asize = 1, Bsize = 1 too |
983 | dec ecx ; if asize = 1, bsize = 1 too |
Line 984... | Line 984... | ||
984 | jz .done |
984 | jz .done |
985 | 985 | ||
986 | ; Prepare to enter loop1 |
986 | ; Prepare to enter loop1 |
987 | mov eax, [asize-ebp+esp] |
987 | mov eax, [asize-ebp+esp] |
988 | 988 | ||
989 | mov ebx, edx |
989 | mov ebx, edx |
990 | lea esi, [esi + eax * 4] ; make A ptr point at end |
990 | lea esi, [esi + eax * 4] ; make a ptr point at end |
991 | lea edi, [edi + eax * 4] ; offset D ptr by Asize |
991 | lea edi, [edi + eax * 4] ; offset dst ptr by asize |
992 | neg ecx ; negate j size/index for inner loop |
992 | neg ecx ; negate j size/index for inner loop |
Line 1007... | Line 1007... | ||
1007 | mov eax, [bsize-ebp+esp] |
1007 | mov eax, [bsize-ebp+esp] |
1008 | mov [edi], ebx ; most significant dword of the product |
1008 | mov [edi], ebx ; most significant dword of the product |
1009 | add edi, 4 ; increment dst |
1009 | add edi, 4 ; increment dst |
1010 | dec eax |
1010 | dec eax |
1011 | jz .skip |
1011 | jz .skip |
1012 | mov [counter-ebp+esp], eax ; set index i to Bsize |
1012 | mov [counter-ebp+esp], eax ; set index i to bsize |
Line 1013... | Line 1013... | ||
1013 | 1013 | ||
1014 | .outer: |
1014 | .outer: |
1015 | add ebp, 4 ; make ebp point to next B dword |
1015 | add ebp, 4 ; make ebp point to next b dword |
1016 | mov ecx, [asize-ebp+esp] |
1016 | mov ecx, [asize-ebp+esp] |
1017 | neg ecx |
1017 | neg ecx |
Line 1018... | Line 1018... | ||
1018 | xor ebx, ebx |
1018 | xor ebx, ebx |
Line 1045... | Line 1045... | ||
1045 | mov esp, [esp_] |
1045 | mov esp, [esp_] |
Line 1046... | Line 1046... | ||
1046 | 1046 | ||
Line 1047... | Line 1047... | ||
1047 | ret |
1047 | ret |
1048 | 1048 | ||
1049 | .done: |
1049 | .done: |
1050 | mov [edi+4], edx ; store to D[1] |
1050 | mov [edi+4], edx ; store to dst[1] |
1051 | ; restore esp, ebp |
1051 | ; restore esp, ebp |
Line 1052... | Line 1052... | ||
1052 | mov ebp, esp |
1052 | mov ebp, esp |
Line 1149... | Line 1149... | ||
1149 | ret |
1149 | ret |
Line 1150... | Line 1150... | ||
1150 | 1150 | ||
Line 1151... | Line 1151... | ||
1151 | endp |
1151 | endp |
1152 | 1152 | ||
1153 | ;;===========================================================================;; |
1153 | ;;===========================================================================;; |
1154 | proc mpint_modexp uses edi eax ebx ecx edx, dst, b, e, m ;///////////////////;; |
1154 | proc mpint_modexp uses edi eax ebx ecx edx, dest, b, e, m ;//////////////////;; |
1155 | ;;---------------------------------------------------------------------------;; |
1155 | ;;---------------------------------------------------------------------------;; |
1156 | ;? Find the modulo (remainder after division) of dst by mod. ;; |
1156 | ;? Find the modulo (remainder after division) of dst by mod. ;; |
1157 | ;;---------------------------------------------------------------------------;; |
1157 | ;;---------------------------------------------------------------------------;; |
Line 1162... | Line 1162... | ||
1162 | ;;---------------------------------------------------------------------------;; |
1162 | ;;---------------------------------------------------------------------------;; |
1163 | ;< dst = b ** e MOD m ;; |
1163 | ;< dst = b ** e MOD m ;; |
1164 | ;;===========================================================================;; |
1164 | ;;===========================================================================;; |
Line 1165... | Line 1165... | ||
1165 | 1165 | ||
- | 1166 | locals |
|
- | 1167 | dst1 dd ? |
|
1166 | locals |
1168 | dst2 dd ? |
1167 | mpint_tmp rb MPINT_MAX_LEN+4 |
1169 | tmp rb MPINT_MAX_LEN+4 |
Line 1168... | Line 1170... | ||
1168 | endl |
1170 | endl |
Line 1169... | Line 1171... | ||
1169 | 1171 | ||
1170 | DEBUGF 1, "mpint_modexp(0x%x, 0x%x, 0x%x, 0x%x)\n", [dst], [b], [e], [m] |
1172 | DEBUGF 1, "mpint_modexp(0x%x, 0x%x, 0x%x, 0x%x)\n", [dest], [b], [e], [m] |
1171 | 1173 | ||
1172 | ; If mod is zero, return |
1174 | ; If mod is zero, return |
Line 1183... | Line 1185... | ||
1183 | jz .exp_zero |
1185 | jz .exp_zero |
1184 | mov ecx, eax |
1186 | mov ecx, eax |
1185 | mov edi, [e] |
1187 | mov edi, [e] |
1186 | lea edi, [edi + 4 + ecx - 1] |
1188 | lea edi, [edi + 4 + ecx - 1] |
Line -... | Line 1189... | ||
- | 1189 | ||
- | 1190 | ; Set up temp variables |
|
- | 1191 | lea eax, [tmp] |
|
- | 1192 | mov edx, [dest] |
|
- | 1193 | mov [dst1], eax |
|
- | 1194 | mov [dst2], edx |
|
1187 | 1195 | ||
1188 | ; Find the highest order bit in this byte |
1196 | ; Find the highest order bit in this byte |
1189 | mov al, [edi] |
1197 | mov al, [edi] |
1190 | test al, al |
1198 | test al, al |
1191 | jz .invalid |
1199 | jz .invalid |
1192 | mov bl, 9 |
1200 | mov bl, 9 |
1193 | @@: |
1201 | @@: |
1194 | dec bl |
1202 | dec bl |
1195 | shl al, 1 |
1203 | shl al, 1 |
Line 1196... | Line -... | ||
1196 | jnc @r |
- | |
1197 | - | ||
1198 | ; Make pointer to tmp mpint for convenient access |
- | |
1199 | lea edx, [mpint_tmp] |
1204 | jnc @r |
1200 | 1205 | ||
1201 | ; Initialise result to base, to take care of the highest order bit |
1206 | ; Initialise result to base, to take care of the highest order bit |
1202 | stdcall mpint_mov, [dst], [b] |
1207 | stdcall mpint_mov, [dst1], [b] |
1203 | dec bl |
1208 | dec bl |
1204 | jz .next_byte |
1209 | jz .next_byte |
1205 | .bit_loop: |
- | |
1206 | ; For each bit, square result |
1210 | .bit_loop: |
1207 | stdcall mpint_mov, edx, [dst] |
1211 | ; For each bit, square result |
Line 1208... | Line 1212... | ||
1208 | stdcall mpint_mul, [dst], edx, edx |
1212 | stdcall mpint_mul, [dst2], [dst1], [dst1] |
1209 | stdcall mpint_mod, [dst], [m] |
1213 | stdcall mpint_mod, [dst2], [m] |
1210 | 1214 | ||
1211 | ; If the bit is set, multiply result by the base |
1215 | ; If the bit is set, multiply result by the base |
1212 | shl al, 1 |
1216 | shl al, 1 |
- | 1217 | jnc .bit_zero |
|
1213 | jnc .next_bit |
1218 | stdcall mpint_mul, [dst1], [b], [dst2] |
- | 1219 | stdcall mpint_mod, [dst1], [m] |
|
- | 1220 | dec bl |
|
1214 | stdcall mpint_mov, edx, [dst] |
1221 | jnz .bit_loop |
- | 1222 | jmp .next_byte |
|
- | 1223 | ||
- | 1224 | .bit_zero: |
|
- | 1225 | mov edx, [dst1] |
|
1215 | stdcall mpint_mul, [dst], [b], edx |
1226 | mov esi, [dst2] |
1216 | stdcall mpint_mod, [dst], [m] |
1227 | mov [dst2], edx |
- | 1228 | mov [dst1], esi |
|
1217 | .next_bit: |
1229 | dec bl |
1218 | dec bl |
1230 | jnz .bit_loop |
1219 | jnz .bit_loop |
1231 | |
1220 | .next_byte: |
1232 | .next_byte: |
1221 | dec ecx |
1233 | dec ecx |
1222 | jz .done |
1234 | jz .done |
1223 | dec edi |
1235 | dec edi |
1224 | mov al, [edi] |
1236 | mov al, [edi] |
- | 1237 | mov bl, 8 |
|
- | 1238 | jmp .bit_loop |
|
- | 1239 | .done: |
|
- | 1240 | mov edx, [dest] |
|
- | 1241 | cmp edx, [dst1] |
|
- | 1242 | je @f |
|
1225 | mov bl, 8 |
1243 | stdcall mpint_mov, [dest], [dst1] |
Line 1226... | Line 1244... | ||
1226 | jmp .bit_loop |
1244 | @@: |
1227 | .done: |
1245 | |
1228 | ret |
1246 | ret |
1229 | 1247 | ||
1230 | .mod_zero: |
1248 | .mod_zero: |
1231 | DEBUGF 3, "modexp with modulo 0\n" |
1249 | DEBUGF 3, "modexp with modulo 0\n" |
Line 1232... | Line 1250... | ||
1232 | ; if mod is zero, result = 0 |
1250 | ; if mod is zero, result = 0 |
1233 | mov eax, [dst] |
1251 | mov eax, [dest] |
1234 | mov dword[eax], 0 |
1252 | mov dword[eax], 0 |
1235 | ret |
1253 | ret |
1236 | 1254 | ||
1237 | .exp_zero: |
1255 | .exp_zero: |
1238 | DEBUGF 3, "modexp with exponent 0\n" |
1256 | DEBUGF 3, "modexp with exponent 0\n" |
Line 1239... | Line 1257... | ||
1239 | ; if exponent is zero, result = 1 |
1257 | ; if exponent is zero, result = 1 |
Line 1252... | Line 1270... | ||
1252 | stdcall mpint_grow, [m], eax |
1270 | stdcall mpint_grow, [m], eax |
1253 | jmp .modsize_ok |
1271 | jmp .modsize_ok |
Line 1254... | Line 1272... | ||
1254 | 1272 | ||
Line -... | Line 1273... | ||
- | 1273 | endp>>>>>>>>>>>>>>>>>> |