VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/math/bignum.cpp@ 76452

Last change on this file since 76452 was 73665, checked in by vboxsync, 6 years ago

IPRT,SUP,Main: Working on new crypto key handling and rsa signing. bugref:9152
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 94.6 KB
Line 
1/* $Id: bignum.cpp 73665 2018-08-14 17:49:23Z vboxsync $ */
2/** @file
3 * IPRT - Big Integer Numbers.
4 */
5
6/*
7 * Copyright (C) 2006-2017 Oracle Corporation
8 *
9 * This file is part of VirtualBox Open Source Edition (OSE), as
10 * available from http://www.virtualbox.org. This file is free software;
11 * you can redistribute it and/or modify it under the terms of the GNU
12 * General Public License (GPL) as published by the Free Software
13 * Foundation, in version 2 as it comes in the "COPYING" file of the
14 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16 *
17 * The contents of this file may alternatively be used under the terms
18 * of the Common Development and Distribution License Version 1.0
19 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20 * VirtualBox OSE distribution, in which case the provisions of the
21 * CDDL are applicable instead of those of the GPL.
22 *
23 * You may elect to license modified versions of this file under the
24 * terms and conditions of either the GPL or the CDDL or both.
25 */
26
27
28/*********************************************************************************************************************************
29* Header Files *
30*********************************************************************************************************************************/
31/*#ifdef IN_RING3
32# define RTMEM_WRAP_TO_EF_APIS
33#endif*/
34#include "internal/iprt.h"
35#include <iprt/bignum.h>
36
37#include <iprt/asm.h>
38#include <iprt/asm-math.h>
39#include <iprt/err.h>
40#include <iprt/mem.h>
41#include <iprt/memsafer.h>
42#include <iprt/string.h>
43#if RTBIGNUM_ELEMENT_BITS == 64
44# include <iprt/uint128.h>
45#endif
46
47
48/*********************************************************************************************************************************
49* Defined Constants And Macros *
50*********************************************************************************************************************************/
51/** Allocation alignment in elements. */
52#ifndef RTMEM_WRAP_TO_EF_APIS
53# define RTBIGNUM_ALIGNMENT 4U
54#else
55# define RTBIGNUM_ALIGNMENT 1U
56#endif
57
58/** The max size (in bytes) of an elements array. */
59#define RTBIGNUM_MAX_SIZE _4M
60
61
62/** Assert the validity of a big number structure pointer in strict builds. */
63#ifdef RT_STRICT
64# define RTBIGNUM_ASSERT_VALID(a_pBigNum) \
65 do { \
66 AssertPtr(a_pBigNum); \
67 Assert(!(a_pBigNum)->fCurScrambled); \
68 Assert( (a_pBigNum)->cUsed == (a_pBigNum)->cAllocated \
69 || ASMMemIsZero(&(a_pBigNum)->pauElements[(a_pBigNum)->cUsed], \
70 ((a_pBigNum)->cAllocated - (a_pBigNum)->cUsed) * RTBIGNUM_ELEMENT_SIZE)); \
71 } while (0)
72#else
73# define RTBIGNUM_ASSERT_VALID(a_pBigNum) do {} while (0)
74#endif
75
76
77/** Enable assembly optimizations. */
78#if defined(RT_ARCH_AMD64) || defined(RT_ARCH_X86)
79# define IPRT_BIGINT_WITH_ASM
80#endif
81
82
83/** @def RTBIGNUM_ZERO_ALIGN
84 * For calculating the rtBigNumEnsureExtraZeroElements argument from cUsed.
85 * This has to do with 64-bit assembly instruction operating as RTBIGNUMELEMENT
86 * was 64-bit on some hosts.
87 */
88#if defined(IPRT_BIGINT_WITH_ASM) && ARCH_BITS == 64 && RTBIGNUM_ELEMENT_SIZE == 4 && defined(RT_LITTLE_ENDIAN)
89# define RTBIGNUM_ZERO_ALIGN(a_cUsed) RT_ALIGN_32(a_cUsed, 2)
90#elif defined(IPRT_BIGINT_WITH_ASM)
91# define RTBIGNUM_ZERO_ALIGN(a_cUsed) (a_cUsed)
92#else
93# define RTBIGNUM_ZERO_ALIGN(a_cUsed) (a_cUsed)
94#endif
95
96#define RTBIGNUMELEMENT_HALF_MASK ( ((RTBIGNUMELEMENT)1 << (RTBIGNUM_ELEMENT_BITS / 2)) - (RTBIGNUMELEMENT)1)
97#define RTBIGNUMELEMENT_LO_HALF(a_uElement) ( (RTBIGNUMELEMENT_HALF_MASK) & (a_uElement) )
98#define RTBIGNUMELEMENT_HI_HALF(a_uElement) ( (a_uElement) >> (RTBIGNUM_ELEMENT_BITS / 2) )
99
100
101/*********************************************************************************************************************************
102* Structures and Typedefs *
103*********************************************************************************************************************************/
104/** Type the size of two elements. */
105#if RTBIGNUM_ELEMENT_BITS == 64
106typedef RTUINT128U RTBIGNUMELEMENT2X;
107#else
108typedef RTUINT64U RTBIGNUMELEMENT2X;
109#endif
110
111
112/*********************************************************************************************************************************
113* Internal Functions *
114*********************************************************************************************************************************/
115DECLINLINE(int) rtBigNumSetUsed(PRTBIGNUM pBigNum, uint32_t cNewUsed);
116
117#ifdef IPRT_BIGINT_WITH_ASM
118/* bignum-amd64-x86.asm: */
119DECLASM(void) rtBigNumMagnitudeSubAssemblyWorker(RTBIGNUMELEMENT *pauResult, RTBIGNUMELEMENT const *pauMinuend,
120 RTBIGNUMELEMENT const *pauSubtrahend, uint32_t cUsed);
121DECLASM(void) rtBigNumMagnitudeSubThisAssemblyWorker(RTBIGNUMELEMENT *pauMinuendResult, RTBIGNUMELEMENT const *pauSubtrahend,
122 uint32_t cUsed);
123DECLASM(RTBIGNUMELEMENT) rtBigNumMagnitudeShiftLeftOneAssemblyWorker(RTBIGNUMELEMENT *pauElements, uint32_t cUsed,
124 RTBIGNUMELEMENT uCarry);
125DECLASM(void) rtBigNumElement2xDiv2xBy1x(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT *puRemainder,
126 RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo, RTBIGNUMELEMENT uDivisor);
127DECLASM(void) rtBigNumMagnitudeMultiplyAssemblyWorker(PRTBIGNUMELEMENT pauResult,
128 PCRTBIGNUMELEMENT pauMultiplier, uint32_t cMultiplier,
129 PCRTBIGNUMELEMENT pauMultiplicand, uint32_t cMultiplicand);
130#endif
131
132
133
134
135
136/** @name Functions working on one element.
137 * @{ */
138
139DECLINLINE(uint32_t) rtBigNumElementBitCount(RTBIGNUMELEMENT uElement)
140{
141#if RTBIGNUM_ELEMENT_SIZE == 8
142 if (uElement >> 32)
143 return ASMBitLastSetU32((uint32_t)(uElement >> 32)) + 32;
144 return ASMBitLastSetU32((uint32_t)uElement);
145#elif RTBIGNUM_ELEMENT_SIZE == 4
146 return ASMBitLastSetU32(uElement);
147#else
148# error "Bad RTBIGNUM_ELEMENT_SIZE value"
149#endif
150}
151
152
153/**
154 * Does addition with carry.
155 *
156 * This is a candidate for inline assembly on some platforms.
157 *
158 * @returns The result (the sum)
159 * @param uAugend What to add to.
160 * @param uAddend What to add to it.
161 * @param pfCarry Where to read the input carry and return the output
162 * carry.
163 */
164DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementAddWithCarry(RTBIGNUMELEMENT uAugend, RTBIGNUMELEMENT uAddend,
165 RTBIGNUMELEMENT *pfCarry)
166{
167 RTBIGNUMELEMENT uRet = uAugend + uAddend;
168 if (!*pfCarry)
169 *pfCarry = uRet < uAugend;
170 else
171 {
172 uRet += 1;
173 *pfCarry = uRet <= uAugend;
174 }
175 return uRet;
176}
177
178
179#if !defined(IPRT_BIGINT_WITH_ASM) || defined(RT_STRICT)
180/**
181 * Does addition with borrow.
182 *
183 * This is a candidate for inline assembly on some platforms.
184 *
185 * @returns The result (the sum)
186 * @param uMinuend What to subtract from.
187 * @param uSubtrahend What to subtract.
188 * @param pfBorrow Where to read the input borrow and return the output
189 * borrow.
190 */
191DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementSubWithBorrow(RTBIGNUMELEMENT uMinuend, RTBIGNUMELEMENT uSubtrahend,
192 RTBIGNUMELEMENT *pfBorrow)
193{
194 RTBIGNUMELEMENT uRet = uMinuend - uSubtrahend - *pfBorrow;
195
196 /* Figure out if we borrowed. */
197 *pfBorrow = !*pfBorrow ? uMinuend < uSubtrahend : uMinuend <= uSubtrahend;
198 return uRet;
199}
200#endif
201
202/** @} */
203
204
205
206
207/** @name Double element primitives.
208 * @{ */
209
210static int rtBigNumElement2xCopyToMagnitude(RTBIGNUMELEMENT2X const *pValue2x, PRTBIGNUM pDst)
211{
212 int rc;
213 if (pValue2x->s.Hi)
214 {
215 rc = rtBigNumSetUsed(pDst, 2);
216 if (RT_SUCCESS(rc))
217 {
218 pDst->pauElements[0] = pValue2x->s.Lo;
219 pDst->pauElements[1] = pValue2x->s.Hi;
220 }
221 }
222 else if (pValue2x->s.Lo)
223 {
224 rc = rtBigNumSetUsed(pDst, 1);
225 if (RT_SUCCESS(rc))
226 pDst->pauElements[0] = pValue2x->s.Lo;
227 }
228 else
229 rc = rtBigNumSetUsed(pDst, 0);
230 return rc;
231}
232
233static void rtBigNumElement2xDiv(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT2X *puRemainder,
234 RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo,
235 RTBIGNUMELEMENT uDivisorHi, RTBIGNUMELEMENT uDivisorLo)
236{
237 RTBIGNUMELEMENT2X uDividend;
238 uDividend.s.Lo = uDividendLo;
239 uDividend.s.Hi = uDividendHi;
240
241 RTBIGNUMELEMENT2X uDivisor;
242 uDivisor.s.Lo = uDivisorLo;
243 uDivisor.s.Hi = uDivisorHi;
244
245#if RTBIGNUM_ELEMENT_BITS == 64
246 RTUInt128DivRem(puQuotient, puRemainder, &uDividend, &uDivisor);
247#else
248 puQuotient->u = uDividend.u / uDivisor.u;
249 puRemainder->u = uDividend.u % uDivisor.u;
250#endif
251}
252
253#ifndef IPRT_BIGINT_WITH_ASM
254static void rtBigNumElement2xDiv2xBy1x(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT *puRemainder,
255 RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo, RTBIGNUMELEMENT uDivisor)
256{
257 RTBIGNUMELEMENT2X uDividend;
258 uDividend.s.Lo = uDividendLo;
259 uDividend.s.Hi = uDividendHi;
260
261# if RTBIGNUM_ELEMENT_BITS == 64
262 RTBIGNUMELEMENT2X uRemainder2x;
263 RTBIGNUMELEMENT2X uDivisor2x;
264 uDivisor2x.s.Hi = 0;
265 uDivisor2x.s.Lo = uDivisor;
266 /** @todo optimize this. */
267 RTUInt128DivRem(puQuotient, &uRemainder2x, &uDividend, &uDivisor2x);
268 *puRemainder = uRemainder2x.s.Lo;
269# else
270 puQuotient->u = uDividend.u / uDivisor;
271 puRemainder->u = uDividend.u % uDivisor;
272# endif
273}
274#endif
275
276DECLINLINE(void) rtBigNumElement2xDec(RTBIGNUMELEMENT2X *puValue)
277{
278#if RTBIGNUM_ELEMENT_BITS == 64
279 if (puValue->s.Lo-- == 0)
280 puValue->s.Hi--;
281#else
282 puValue->u -= 1;
283#endif
284}
285
286#if 0 /* unused */
287DECLINLINE(void) rtBigNumElement2xAdd1x(RTBIGNUMELEMENT2X *puValue, RTBIGNUMELEMENT uAdd)
288{
289#if RTBIGNUM_ELEMENT_BITS == 64
290 RTUInt128AssignAddU64(puValue, uAdd);
291#else
292 puValue->u += uAdd;
293#endif
294}
295#endif /* unused */
296
297/** @} */
298
299
300
301
302
303/**
304 * Scrambles a big number if required.
305 *
306 * @param pBigNum The big number.
307 */
308DECLINLINE(void) rtBigNumScramble(PRTBIGNUM pBigNum)
309{
310 if (pBigNum->fSensitive)
311 {
312 AssertReturnVoid(!pBigNum->fCurScrambled);
313 if (pBigNum->pauElements)
314 {
315 int rc = RTMemSaferScramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
316 pBigNum->fCurScrambled = RT_SUCCESS(rc);
317 }
318 else
319 pBigNum->fCurScrambled = true;
320 }
321}
322
323
324/**
325 * Unscrambles a big number if required.
326 *
327 * @returns IPRT status code.
328 * @param pBigNum The big number.
329 */
330DECLINLINE(int) rtBigNumUnscramble(PRTBIGNUM pBigNum)
331{
332 if (pBigNum->fSensitive)
333 {
334 AssertReturn(pBigNum->fCurScrambled, VERR_INTERNAL_ERROR_2);
335 if (pBigNum->pauElements)
336 {
337 int rc = RTMemSaferUnscramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
338 pBigNum->fCurScrambled = !RT_SUCCESS(rc);
339 return rc;
340 }
341 else
342 pBigNum->fCurScrambled = false;
343 }
344 return VINF_SUCCESS;
345}
346
347
348/**
349 * Getter function for pauElements which extends the array to infinity.
350 *
351 * @returns The element value.
352 * @param pBigNum The big number.
353 * @param iElement The element index.
354 */
355DECLINLINE(RTBIGNUMELEMENT) rtBigNumGetElement(PCRTBIGNUM pBigNum, uint32_t iElement)
356{
357 if (iElement < pBigNum->cUsed)
358 return pBigNum->pauElements[iElement];
359 return 0;
360}
361
362
363/**
364 * Grows the pauElements array so it can fit at least @a cNewUsed entries.
365 *
366 * @returns IPRT status code.
367 * @param pBigNum The big number.
368 * @param cNewUsed The new cUsed value.
369 * @param cMinElements The minimum number of elements.
370 */
371static int rtBigNumGrow(PRTBIGNUM pBigNum, uint32_t cNewUsed, uint32_t cMinElements)
372{
373 Assert(cMinElements >= cNewUsed);
374 uint32_t const cbOld = pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE;
375 uint32_t const cNew = RT_ALIGN_32(cMinElements, RTBIGNUM_ALIGNMENT);
376 uint32_t const cbNew = cNew * RTBIGNUM_ELEMENT_SIZE;
377 Assert(cbNew > cbOld);
378 if (cbNew <= RTBIGNUM_MAX_SIZE && cbNew > cbOld)
379 {
380 void *pvNew;
381 if (pBigNum->fSensitive)
382 pvNew = RTMemSaferReallocZ(cbOld, pBigNum->pauElements, cbNew);
383 else
384 pvNew = RTMemRealloc(pBigNum->pauElements, cbNew);
385 if (RT_LIKELY(pvNew))
386 {
387 if (cbNew > cbOld)
388 RT_BZERO((char *)pvNew + cbOld, cbNew - cbOld);
389 if (pBigNum->cUsed > cNewUsed)
390 RT_BZERO((RTBIGNUMELEMENT *)pvNew + cNewUsed, (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
391
392 pBigNum->pauElements = (RTBIGNUMELEMENT *)pvNew;
393 pBigNum->cUsed = cNewUsed;
394 pBigNum->cAllocated = cNew;
395 return VINF_SUCCESS;
396 }
397 return VERR_NO_MEMORY;
398 }
399 return VERR_OUT_OF_RANGE;
400}
401
402
403/**
404 * Changes the cUsed member, growing the pauElements array if necessary.
405 *
406 * Any elements added to the array will be initialized to zero.
407 *
408 * @returns IPRT status code.
409 * @param pBigNum The big number.
410 * @param cNewUsed The new cUsed value.
411 */
412DECLINLINE(int) rtBigNumSetUsed(PRTBIGNUM pBigNum, uint32_t cNewUsed)
413{
414 if (pBigNum->cAllocated >= cNewUsed)
415 {
416 if (pBigNum->cUsed > cNewUsed)
417 RT_BZERO(&pBigNum->pauElements[cNewUsed], (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
418#ifdef RT_STRICT
419 else if (pBigNum->cUsed != cNewUsed)
420 Assert(ASMMemIsZero(&pBigNum->pauElements[pBigNum->cUsed], (cNewUsed - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE));
421#endif
422 pBigNum->cUsed = cNewUsed;
423 return VINF_SUCCESS;
424 }
425 return rtBigNumGrow(pBigNum, cNewUsed, cNewUsed);
426}
427
428
429/**
430 * Extended version of rtBigNumSetUsed that also allow specifying the number of
431 * zero elements required.
432 *
433 * @returns IPRT status code.
434 * @param pBigNum The big number.
435 * @param cNewUsed The new cUsed value.
436 * @param cMinElements The minimum number of elements allocated. The
437 * difference between @a cNewUsed and @a cMinElements
438 * is initialized to zero because all free elements are
439 * zero.
440 */
441DECLINLINE(int) rtBigNumSetUsedEx(PRTBIGNUM pBigNum, uint32_t cNewUsed, uint32_t cMinElements)
442{
443 if (pBigNum->cAllocated >= cMinElements)
444 {
445 if (pBigNum->cUsed > cNewUsed)
446 RT_BZERO(&pBigNum->pauElements[cNewUsed], (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
447#ifdef RT_STRICT
448 else if (pBigNum->cUsed != cNewUsed)
449 Assert(ASMMemIsZero(&pBigNum->pauElements[pBigNum->cUsed], (cNewUsed - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE));
450#endif
451 pBigNum->cUsed = cNewUsed;
452 return VINF_SUCCESS;
453 }
454 return rtBigNumGrow(pBigNum, cNewUsed, cMinElements);
455}
456
457
458/**
459 * For ensuring zero padding of pauElements for sub/add with carry assembly
460 * operations.
461 *
462 * @returns IPRT status code.
463 * @param pBigNum The big number.
464 * @param cElements The number of elements that must be in the elements
465 * array array, where those after pBigNum->cUsed must
466 * be zero.
467 */
468DECLINLINE(int) rtBigNumEnsureExtraZeroElements(PRTBIGNUM pBigNum, uint32_t cElements)
469{
470 if (pBigNum->cAllocated >= cElements)
471 {
472 Assert( pBigNum->cAllocated == pBigNum->cUsed
473 || ASMMemIsZero(&pBigNum->pauElements[pBigNum->cUsed],
474 (pBigNum->cAllocated - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE));
475 return VINF_SUCCESS;
476 }
477 return rtBigNumGrow(pBigNum, pBigNum->cUsed, cElements);
478}
479
480
481/**
482 * The slow part of rtBigNumEnsureElementPresent where we need to do actual zero
483 * extending.
484 *
485 * @returns IPRT status code.
486 * @param pBigNum The big number.
487 * @param iElement The element we wish to access.
488 */
489static int rtBigNumEnsureElementPresentSlow(PRTBIGNUM pBigNum, uint32_t iElement)
490{
491 uint32_t const cOldUsed = pBigNum->cUsed;
492 int rc = rtBigNumSetUsed(pBigNum, iElement + 1);
493 if (RT_SUCCESS(rc))
494 {
495 RT_BZERO(&pBigNum->pauElements[cOldUsed], (iElement + 1 - cOldUsed) * RTBIGNUM_ELEMENT_SIZE);
496 return VINF_SUCCESS;
497 }
498 return rc;
499}
500
501
502/**
503 * Zero extends the element array to make sure a the specified element index is
504 * accessible.
505 *
506 * This is typically used with bit operations and self modifying methods. Any
507 * new elements added will be initialized to zero. The caller is responsible
508 * for there not being any trailing zero elements.
509 *
510 * The number must be unscrambled.
511 *
512 * @returns IPRT status code.
513 * @param pBigNum The big number.
514 * @param iElement The element we wish to access.
515 */
516DECLINLINE(int) rtBigNumEnsureElementPresent(PRTBIGNUM pBigNum, uint32_t iElement)
517{
518 if (iElement < pBigNum->cUsed)
519 return VINF_SUCCESS;
520 return rtBigNumEnsureElementPresentSlow(pBigNum, iElement);
521}
522
523
524/**
525 * Strips zero elements from the magnitude value.
526 *
527 * @param pBigNum The big number to strip.
528 */
529static void rtBigNumStripTrailingZeros(PRTBIGNUM pBigNum)
530{
531 uint32_t i = pBigNum->cUsed;
532 while (i > 0 && pBigNum->pauElements[i - 1] == 0)
533 i--;
534 pBigNum->cUsed = i;
535}
536
537
538/**
539 * Initialize the big number to zero.
540 *
541 * @returns @a pBigNum
542 * @param pBigNum The big number.
543 * @param fFlags The flags.
544 * @internal
545 */
546DECLINLINE(PRTBIGNUM) rtBigNumInitZeroInternal(PRTBIGNUM pBigNum, uint32_t fFlags)
547{
548 RT_ZERO(*pBigNum);
549 pBigNum->fSensitive = RT_BOOL(fFlags & RTBIGNUMINIT_F_SENSITIVE);
550 return pBigNum;
551}
552
553
554/**
555 * Initialize the big number to zero from a template variable.
556 *
557 * @returns @a pBigNum
558 * @param pBigNum The big number.
559 * @param pTemplate The template big number.
560 * @internal
561 */
562DECLINLINE(PRTBIGNUM) rtBigNumInitZeroTemplate(PRTBIGNUM pBigNum, PCRTBIGNUM pTemplate)
563{
564 RT_ZERO(*pBigNum);
565 pBigNum->fSensitive = pTemplate->fSensitive;
566 return pBigNum;
567}
568
569
570RTDECL(int) RTBigNumInit(PRTBIGNUM pBigNum, uint32_t fFlags, void const *pvRaw, size_t cbRaw)
571{
572 /*
573 * Validate input.
574 */
575 AssertPtrReturn(pBigNum, VERR_INVALID_POINTER);
576 AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_BIG) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE),
577 VERR_INVALID_PARAMETER);
578 AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_UNSIGNED) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_SIGNED), VERR_INVALID_PARAMETER);
579 if (cbRaw)
580 AssertPtrReturn(pvRaw, VERR_INVALID_POINTER);
581
582 /*
583 * Initalize the big number to zero.
584 */
585 rtBigNumInitZeroInternal(pBigNum, fFlags);
586
587 /*
588 * Strip the input and figure the sign flag.
589 */
590 uint8_t const *pb = (uint8_t const *)pvRaw;
591 if (cbRaw)
592 {
593 if (fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE)
594 {
595 if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
596 {
597 while (cbRaw > 0 && pb[cbRaw - 1] == 0)
598 cbRaw--;
599 }
600 else
601 {
602 if (pb[cbRaw - 1] >> 7)
603 {
604 pBigNum->fNegative = 1;
605 while (cbRaw > 1 && pb[cbRaw - 1] == 0xff)
606 cbRaw--;
607 }
608 else
609 while (cbRaw > 0 && pb[cbRaw - 1] == 0)
610 cbRaw--;
611 }
612 }
613 else
614 {
615 if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
616 {
617 while (cbRaw > 0 && *pb == 0)
618 pb++, cbRaw--;
619 }
620 else
621 {
622 if (*pb >> 7)
623 {
624 pBigNum->fNegative = 1;
625 while (cbRaw > 1 && *pb == 0xff)
626 pb++, cbRaw--;
627 }
628 else
629 while (cbRaw > 0 && *pb == 0)
630 pb++, cbRaw--;
631 }
632 }
633 }
634
635 /*
636 * Allocate memory for the elements.
637 */
638 size_t cbAligned = RT_ALIGN_Z(cbRaw, RTBIGNUM_ELEMENT_SIZE);
639 if (RT_UNLIKELY(cbAligned >= RTBIGNUM_MAX_SIZE))
640 return VERR_OUT_OF_RANGE;
641 pBigNum->cUsed = (uint32_t)cbAligned / RTBIGNUM_ELEMENT_SIZE;
642 if (pBigNum->cUsed)
643 {
644 pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, RTBIGNUM_ALIGNMENT);
645 if (pBigNum->fSensitive)
646 pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemSaferAllocZ(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
647 else
648 pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemAlloc(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
649 if (RT_UNLIKELY(!pBigNum->pauElements))
650 return VERR_NO_MEMORY;
651
652 /*
653 * Initialize the array.
654 */
655 uint32_t i = 0;
656 if (fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE)
657 {
658 while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
659 {
660#if RTBIGNUM_ELEMENT_SIZE == 8
661 pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[0], pb[1], pb[2], pb[3], pb[4], pb[5], pb[6], pb[7]);
662#elif RTBIGNUM_ELEMENT_SIZE == 4
663 pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[0], pb[1], pb[2], pb[3]);
664#else
665# error "Bad RTBIGNUM_ELEMENT_SIZE value"
666#endif
667 i++;
668 pb += RTBIGNUM_ELEMENT_SIZE;
669 cbRaw -= RTBIGNUM_ELEMENT_SIZE;
670 }
671
672 if (cbRaw > 0)
673 {
674 RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
675 switch (cbRaw)
676 {
677 default: AssertFailed();
678#if RTBIGNUM_ELEMENT_SIZE == 8
679 RT_FALL_THRU();
680 case 7: uLast = (uLast << 8) | pb[6]; RT_FALL_THRU();
681 case 6: uLast = (uLast << 8) | pb[5]; RT_FALL_THRU();
682 case 5: uLast = (uLast << 8) | pb[4]; RT_FALL_THRU();
683 case 4: uLast = (uLast << 8) | pb[3];
684#endif
685 RT_FALL_THRU();
686 case 3: uLast = (uLast << 8) | pb[2]; RT_FALL_THRU();
687 case 2: uLast = (uLast << 8) | pb[1]; RT_FALL_THRU();
688 case 1: uLast = (uLast << 8) | pb[0];
689 }
690 pBigNum->pauElements[i] = uLast;
691 }
692 }
693 else
694 {
695 pb += cbRaw;
696 while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
697 {
698 pb -= RTBIGNUM_ELEMENT_SIZE;
699#if RTBIGNUM_ELEMENT_SIZE == 8
700 pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[7], pb[6], pb[5], pb[4], pb[3], pb[2], pb[1], pb[0]);
701#elif RTBIGNUM_ELEMENT_SIZE == 4
702 pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[3], pb[2], pb[1], pb[0]);
703#else
704# error "Bad RTBIGNUM_ELEMENT_SIZE value"
705#endif
706 i++;
707 cbRaw -= RTBIGNUM_ELEMENT_SIZE;
708 }
709
710 if (cbRaw > 0)
711 {
712 RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
713 pb -= cbRaw;
714 switch (cbRaw)
715 {
716 default: AssertFailed();
717#if RTBIGNUM_ELEMENT_SIZE == 8
718 RT_FALL_THRU();
719 case 7: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
720 case 6: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
721 case 5: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
722 case 4: uLast = (uLast << 8) | *pb++;
723#endif
724 RT_FALL_THRU();
725 case 3: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
726 case 2: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
727 case 1: uLast = (uLast << 8) | *pb++;
728 }
729 pBigNum->pauElements[i] = uLast;
730 }
731 }
732
733 /*
734 * If negative, negate it so we get a positive magnitude value in pauElements.
735 */
736 if (pBigNum->fNegative)
737 {
738 pBigNum->pauElements[0] = 0U - pBigNum->pauElements[0];
739 for (i = 1; i < pBigNum->cUsed; i++)
740 pBigNum->pauElements[i] = 0U - pBigNum->pauElements[i] - 1U;
741 }
742
743 /*
744 * Clear unused elements.
745 */
746 if (pBigNum->cUsed != pBigNum->cAllocated)
747 {
748 RTBIGNUMELEMENT *puUnused = &pBigNum->pauElements[pBigNum->cUsed];
749 AssertCompile(RTBIGNUM_ALIGNMENT <= 4);
750 switch (pBigNum->cAllocated - pBigNum->cUsed)
751 {
752 default: AssertFailed(); RT_FALL_THRU();
753 case 3: *puUnused++ = 0; RT_FALL_THRU();
754 case 2: *puUnused++ = 0; RT_FALL_THRU();
755 case 1: *puUnused++ = 0;
756 }
757 }
758 RTBIGNUM_ASSERT_VALID(pBigNum);
759 }
760
761 rtBigNumScramble(pBigNum);
762 return VINF_SUCCESS;
763}
764
765
766RTDECL(int) RTBigNumInitZero(PRTBIGNUM pBigNum, uint32_t fFlags)
767{
768 AssertReturn(!(fFlags & ~RTBIGNUMINIT_F_SENSITIVE), VERR_INVALID_PARAMETER);
769 AssertPtrReturn(pBigNum, VERR_INVALID_POINTER);
770
771 rtBigNumInitZeroInternal(pBigNum, fFlags);
772 rtBigNumScramble(pBigNum);
773 return VINF_SUCCESS;
774}
775
776
777/**
778 * Internal clone function that assumes the caller takes care of scrambling.
779 *
780 * @returns IPRT status code.
781 * @param pBigNum The target number.
782 * @param pSrc The source number.
783 */
784static int rtBigNumCloneInternal(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
785{
786 Assert(!pSrc->fCurScrambled);
787 int rc = VINF_SUCCESS;
788
789 /*
790 * Copy over the data.
791 */
792 RT_ZERO(*pBigNum);
793 pBigNum->fNegative = pSrc->fNegative;
794 pBigNum->fSensitive = pSrc->fSensitive;
795 pBigNum->cUsed = pSrc->cUsed;
796 if (pSrc->cUsed)
797 {
798 /* Duplicate the element array. */
799 pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, RTBIGNUM_ALIGNMENT);
800 if (pBigNum->fSensitive)
801 pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemSaferAllocZ(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
802 else
803 pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemAlloc(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
804 if (RT_LIKELY(pBigNum->pauElements))
805 {
806 memcpy(pBigNum->pauElements, pSrc->pauElements, pBigNum->cUsed * RTBIGNUM_ELEMENT_SIZE);
807 if (pBigNum->cUsed != pBigNum->cAllocated)
808 RT_BZERO(&pBigNum->pauElements[pBigNum->cUsed], (pBigNum->cAllocated - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE);
809 }
810 else
811 {
812 RT_ZERO(*pBigNum);
813 rc = VERR_NO_MEMORY;
814 }
815 }
816 return rc;
817}
818
819
820RTDECL(int) RTBigNumClone(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
821{
822 int rc = rtBigNumUnscramble((PRTBIGNUM)pSrc);
823 if (RT_SUCCESS(rc))
824 {
825 RTBIGNUM_ASSERT_VALID(pSrc);
826 rc = rtBigNumCloneInternal(pBigNum, pSrc);
827 if (RT_SUCCESS(rc))
828 rtBigNumScramble(pBigNum);
829 rtBigNumScramble((PRTBIGNUM)pSrc);
830 }
831 return rc;
832}
833
834
835RTDECL(int) RTBigNumDestroy(PRTBIGNUM pBigNum)
836{
837 if (pBigNum)
838 {
839 if (pBigNum->pauElements)
840 {
841 Assert(pBigNum->cAllocated > 0);
842 if (!pBigNum->fSensitive)
843 RTMemFree(pBigNum->pauElements);
844 else
845 {
846 RTMemSaferFree(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
847 RT_ZERO(*pBigNum);
848 }
849 pBigNum->pauElements = NULL;
850 }
851 }
852 return VINF_SUCCESS;
853}
854
855
856RTDECL(int) RTBigNumAssign(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
857{
858 AssertReturn(pDst->fSensitive >= pSrc->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
859 int rc = rtBigNumUnscramble(pDst);
860 if (RT_SUCCESS(rc))
861 {
862 RTBIGNUM_ASSERT_VALID(pDst);
863 rc = rtBigNumUnscramble((PRTBIGNUM)pSrc);
864 if (RT_SUCCESS(rc))
865 {
866 RTBIGNUM_ASSERT_VALID(pSrc);
867 if ( pDst->fSensitive == pSrc->fSensitive
868 || pDst->fSensitive)
869 {
870 if (pDst->cAllocated >= pSrc->cUsed)
871 {
872 if (pDst->cUsed > pSrc->cUsed)
873 RT_BZERO(&pDst->pauElements[pSrc->cUsed], (pDst->cUsed - pSrc->cUsed) * RTBIGNUM_ELEMENT_SIZE);
874 pDst->cUsed = pSrc->cUsed;
875 pDst->fNegative = pSrc->fNegative;
876 memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
877 }
878 else
879 {
880 rc = rtBigNumGrow(pDst, pSrc->cUsed, pSrc->cUsed);
881 if (RT_SUCCESS(rc))
882 {
883 pDst->fNegative = pSrc->fNegative;
884 memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
885 }
886 }
887 }
888 else
889 rc = VERR_BIGNUM_SENSITIVE_INPUT;
890 rtBigNumScramble((PRTBIGNUM)pSrc);
891 }
892 rtBigNumScramble(pDst);
893 }
894 return rc;
895}
896
897
898/**
899 * Same as RTBigNumBitWidth, except that it ignore the signed bit.
900 *
901 * The number must be unscrambled.
902 *
903 * @returns The effective width of the magnitude, in bits. Returns 0 if the
904 * value is zero.
905 * @param pBigNum The bit number.
906 */
907static uint32_t rtBigNumMagnitudeBitWidth(PCRTBIGNUM pBigNum)
908{
909 uint32_t idxLast = pBigNum->cUsed;
910 if (idxLast)
911 {
912 idxLast--;
913 RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
914 return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS;
915 }
916 return 0;
917}
918
919
920RTDECL(uint32_t) RTBigNumBitWidth(PCRTBIGNUM pBigNum)
921{
922 uint32_t idxLast = pBigNum->cUsed;
923 if (idxLast)
924 {
925 idxLast--;
926 rtBigNumUnscramble((PRTBIGNUM)pBigNum);
927 RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
928 rtBigNumScramble((PRTBIGNUM)pBigNum);
929 return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS + pBigNum->fNegative;
930 }
931 return 0;
932}
933
934
935RTDECL(uint32_t) RTBigNumByteWidth(PCRTBIGNUM pBigNum)
936{
937 uint32_t cBits = RTBigNumBitWidth(pBigNum);
938 return (cBits + 7) / 8;
939}
940
941
942RTDECL(int) RTBigNumToBytesBigEndian(PCRTBIGNUM pBigNum, void *pvBuf, size_t cbWanted)
943{
944 AssertPtrReturn(pvBuf, VERR_INVALID_POINTER);
945 AssertReturn(cbWanted > 0, VERR_INVALID_PARAMETER);
946
947 int rc = rtBigNumUnscramble((PRTBIGNUM)pBigNum);
948 if (RT_SUCCESS(rc))
949 {
950 RTBIGNUM_ASSERT_VALID(pBigNum);
951 rc = VINF_SUCCESS;
952 if (pBigNum->cUsed != 0)
953 {
954 uint8_t *pbDst = (uint8_t *)pvBuf;
955 pbDst += cbWanted - 1;
956 for (uint32_t i = 0; i < pBigNum->cUsed; i++)
957 {
958 RTBIGNUMELEMENT uElement = pBigNum->pauElements[i];
959 if (pBigNum->fNegative)
960 uElement = (RTBIGNUMELEMENT)0 - uElement - (i > 0);
961 if (cbWanted >= sizeof(uElement))
962 {
963 *pbDst-- = (uint8_t)uElement;
964 uElement >>= 8;
965 *pbDst-- = (uint8_t)uElement;
966 uElement >>= 8;
967 *pbDst-- = (uint8_t)uElement;
968 uElement >>= 8;
969 *pbDst-- = (uint8_t)uElement;
970#if RTBIGNUM_ELEMENT_SIZE == 8
971 uElement >>= 8;
972 *pbDst-- = (uint8_t)uElement;
973 uElement >>= 8;
974 *pbDst-- = (uint8_t)uElement;
975 uElement >>= 8;
976 *pbDst-- = (uint8_t)uElement;
977 uElement >>= 8;
978 *pbDst-- = (uint8_t)uElement;
979#elif RTBIGNUM_ELEMENT_SIZE != 4
980# error "Bad RTBIGNUM_ELEMENT_SIZE value"
981#endif
982 cbWanted -= sizeof(uElement);
983 }
984 else
985 {
986
987 uint32_t cBitsLeft = RTBIGNUM_ELEMENT_BITS;
988 while (cbWanted > 0)
989 {
990 *pbDst-- = (uint8_t)uElement;
991 uElement >>= 8;
992 cBitsLeft -= 8;
993 cbWanted--;
994 }
995 Assert(cBitsLeft > 0); Assert(cBitsLeft < RTBIGNUM_ELEMENT_BITS);
996 if ( i + 1 < pBigNum->cUsed
997 || ( !pBigNum->fNegative
998 ? uElement != 0
999 : uElement != ((RTBIGNUMELEMENT)1 << cBitsLeft) - 1U ) )
1000 rc = VERR_BUFFER_OVERFLOW;
1001 break;
1002 }
1003 }
1004
1005 /* Sign extend the number to the desired output size. */
1006 if (cbWanted > 0)
1007 memset(pbDst - cbWanted, pBigNum->fNegative ? 0 : 0xff, cbWanted);
1008 }
1009 else
1010 RT_BZERO(pvBuf, cbWanted);
1011 rtBigNumScramble((PRTBIGNUM)pBigNum);
1012 }
1013 return rc;
1014}
1015
1016
1017RTDECL(int) RTBigNumCompare(PRTBIGNUM pLeft, PRTBIGNUM pRight)
1018{
1019 int rc = rtBigNumUnscramble(pLeft);
1020 if (RT_SUCCESS(rc))
1021 {
1022 RTBIGNUM_ASSERT_VALID(pLeft);
1023 rc = rtBigNumUnscramble(pRight);
1024 if (RT_SUCCESS(rc))
1025 {
1026 RTBIGNUM_ASSERT_VALID(pRight);
1027 if (pLeft->fNegative == pRight->fNegative)
1028 {
1029 if (pLeft->cUsed == pRight->cUsed)
1030 {
1031 rc = 0;
1032 uint32_t i = pLeft->cUsed;
1033 while (i-- > 0)
1034 if (pLeft->pauElements[i] != pRight->pauElements[i])
1035 {
1036 rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
1037 break;
1038 }
1039 if (pLeft->fNegative)
1040 rc = -rc;
1041 }
1042 else
1043 rc = !pLeft->fNegative
1044 ? pLeft->cUsed < pRight->cUsed ? -1 : 1
1045 : pLeft->cUsed < pRight->cUsed ? 1 : -1;
1046 }
1047 else
1048 rc = pLeft->fNegative ? -1 : 1;
1049
1050 rtBigNumScramble(pRight);
1051 }
1052 rtBigNumScramble(pLeft);
1053 }
1054 return rc;
1055}
1056
1057
1058RTDECL(int) RTBigNumCompareWithU64(PRTBIGNUM pLeft, uint64_t uRight)
1059{
1060 int rc = rtBigNumUnscramble(pLeft);
1061 if (RT_SUCCESS(rc))
1062 {
1063 RTBIGNUM_ASSERT_VALID(pLeft);
1064 if (!pLeft->fNegative)
1065 {
1066 if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(uRight))
1067 {
1068 if (pLeft->cUsed == 0)
1069 rc = uRight == 0 ? 0 : -1;
1070 else
1071 {
1072#if RTBIGNUM_ELEMENT_SIZE == 8
1073 uint64_t uLeft = rtBigNumGetElement(pLeft, 0);
1074 if (uLeft < uRight)
1075 rc = -1;
1076 else
1077 rc = uLeft == uRight ? 0 : 1;
1078#elif RTBIGNUM_ELEMENT_SIZE == 4
1079 uint32_t uSubLeft = rtBigNumGetElement(pLeft, 1);
1080 uint32_t uSubRight = uRight >> 32;
1081 if (uSubLeft == uSubRight)
1082 {
1083 uSubLeft = rtBigNumGetElement(pLeft, 0);
1084 uSubRight = (uint32_t)uRight;
1085 }
1086 if (uSubLeft < uSubRight)
1087 rc = -1;
1088 else
1089 rc = uSubLeft == uSubRight ? 0 : 1;
1090#else
1091# error "Bad RTBIGNUM_ELEMENT_SIZE value"
1092#endif
1093 }
1094 }
1095 else
1096 rc = 1;
1097 }
1098 else
1099 rc = -1;
1100 rtBigNumScramble(pLeft);
1101 }
1102 return rc;
1103}
1104
1105
1106RTDECL(int) RTBigNumCompareWithS64(PRTBIGNUM pLeft, int64_t iRight)
1107{
1108 int rc = rtBigNumUnscramble(pLeft);
1109 if (RT_SUCCESS(rc))
1110 {
1111 RTBIGNUM_ASSERT_VALID(pLeft);
1112 if (pLeft->fNegative == (unsigned)(iRight < 0)) /* (unsigned cast is for MSC weirdness) */
1113 {
1114 AssertCompile(RTBIGNUM_ELEMENT_SIZE <= sizeof(iRight));
1115 if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(iRight))
1116 {
1117 uint64_t uRightMagn = !pLeft->fNegative ? (uint64_t)iRight : (uint64_t)-iRight;
1118#if RTBIGNUM_ELEMENT_SIZE == 8
1119 uint64_t uLeft = rtBigNumGetElement(pLeft, 0);
1120 if (uLeft < uRightMagn)
1121 rc = -1;
1122 else
1123 rc = uLeft == (uint64_t)uRightMagn ? 0 : 1;
1124#elif RTBIGNUM_ELEMENT_SIZE == 4
1125 uint32_t uSubLeft = rtBigNumGetElement(pLeft, 1);
1126 uint32_t uSubRight = uRightMagn >> 32;
1127 if (uSubLeft == uSubRight)
1128 {
1129 uSubLeft = rtBigNumGetElement(pLeft, 0);
1130 uSubRight = (uint32_t)uRightMagn;
1131 }
1132 if (uSubLeft < uSubRight)
1133 rc = -1;
1134 else
1135 rc = uSubLeft == uSubRight ? 0 : 1;
1136#else
1137# error "Bad RTBIGNUM_ELEMENT_SIZE value"
1138#endif
1139 if (pLeft->fNegative)
1140 rc = -rc;
1141 }
1142 else
1143 rc = pLeft->fNegative ? -1 : 1;
1144 }
1145 else
1146 rc = pLeft->fNegative ? -1 : 1;
1147 rtBigNumScramble(pLeft);
1148 }
1149 return rc;
1150}
1151
1152
1153/**
1154 * Compares the magnitude values of two big numbers.
1155 *
1156 * @retval -1 if pLeft is smaller than pRight.
1157 * @retval 0 if pLeft is equal to pRight.
1158 * @retval 1 if pLeft is larger than pRight.
1159 * @param pLeft The left side number.
1160 * @param pRight The right side number.
1161 */
1162static int rtBigNumMagnitudeCompare(PCRTBIGNUM pLeft, PCRTBIGNUM pRight)
1163{
1164 Assert(!pLeft->fCurScrambled); Assert(!pRight->fCurScrambled);
1165 int rc;
1166 uint32_t i = pLeft->cUsed;
1167 if (i == pRight->cUsed)
1168 {
1169 rc = 0;
1170 while (i-- > 0)
1171 if (pLeft->pauElements[i] != pRight->pauElements[i])
1172 {
1173 rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
1174 break;
1175 }
1176 }
1177 else
1178 rc = i < pRight->cUsed ? -1 : 1;
1179 return rc;
1180}
1181
1182
1183/**
1184 * Copies the magnitude of on number (@a pSrc) to another (@a pBigNum).
1185 *
1186 * The variables must be unscrambled. The sign flag is not considered nor
1187 * touched.
1188 *
1189 * @returns IPRT status code.
1190 * @param pDst The destination number.
1191 * @param pSrc The source number.
1192 */
1193DECLINLINE(int) rtBigNumMagnitudeCopy(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
1194{
1195 int rc = rtBigNumSetUsed(pDst, pSrc->cUsed);
1196 if (RT_SUCCESS(rc))
1197 memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
1198 return rc;
1199}
1200
1201
1202
1203/**
1204 * Adds two magnitudes and stores them into a third.
1205 *
1206 * All variables must be unscrambled. The sign flag is not considered nor
1207 * touched.
1208 *
1209 * @returns IPRT status code.
1210 * @param pResult The resultant.
1211 * @param pAugend To whom it shall be addede.
1212 * @param pAddend The nombre to addede.
1213 */
1214static int rtBigNumMagnitudeAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
1215{
1216 Assert(!pResult->fCurScrambled); Assert(!pAugend->fCurScrambled); Assert(!pAddend->fCurScrambled);
1217 Assert(pResult != pAugend); Assert(pResult != pAddend);
1218
1219 uint32_t cElements = RT_MAX(pAugend->cUsed, pAddend->cUsed);
1220 int rc = rtBigNumSetUsed(pResult, cElements);
1221 if (RT_SUCCESS(rc))
1222 {
1223 /*
1224 * The primitive way, requires at least two additions for each entry
1225 * without machine code help.
1226 */
1227 RTBIGNUMELEMENT fCarry = 0;
1228 for (uint32_t i = 0; i < cElements; i++)
1229 pResult->pauElements[i] = rtBigNumElementAddWithCarry(rtBigNumGetElement(pAugend, i),
1230 rtBigNumGetElement(pAddend, i),
1231 &fCarry);
1232 if (fCarry)
1233 {
1234 rc = rtBigNumSetUsed(pResult, cElements + 1);
1235 if (RT_SUCCESS(rc))
1236 pResult->pauElements[cElements++] = 1;
1237 }
1238 Assert(pResult->cUsed == cElements || RT_FAILURE_NP(rc));
1239 }
1240
1241 return rc;
1242}
1243
1244
1245/**
1246 * Substracts a smaller (or equal) magnitude from another one and stores it into
1247 * a third.
1248 *
1249 * All variables must be unscrambled. The sign flag is not considered nor
1250 * touched. For this reason, the @a pMinuend must be larger or equal to @a
1251 * pSubtrahend.
1252 *
1253 * @returns IPRT status code.
1254 * @param pResult There to store the result.
1255 * @param pMinuend What to subtract from.
1256 * @param pSubtrahend What to subtract.
1257 */
1258static int rtBigNumMagnitudeSub(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
1259{
1260 Assert(!pResult->fCurScrambled); Assert(!pMinuend->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
1261 Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
1262 Assert(pMinuend->cUsed >= pSubtrahend->cUsed);
1263
1264 int rc;
1265 if (pSubtrahend->cUsed)
1266 {
1267 /*
1268 * Resize the result. In the assembly case, ensure that all three arrays
1269 * has the same number of used entries, possibly with an extra zero
1270 * element on 64-bit systems.
1271 */
1272 rc = rtBigNumSetUsedEx(pResult, pMinuend->cUsed, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
1273#ifdef IPRT_BIGINT_WITH_ASM
1274 if (RT_SUCCESS(rc))
1275 rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pMinuend, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
1276 if (RT_SUCCESS(rc))
1277 rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pSubtrahend, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
1278#endif
1279 if (RT_SUCCESS(rc))
1280 {
1281#ifdef IPRT_BIGINT_WITH_ASM
1282 /*
1283 * Call assembly to do the work.
1284 */
1285 rtBigNumMagnitudeSubAssemblyWorker(pResult->pauElements, pMinuend->pauElements,
1286 pSubtrahend->pauElements, pMinuend->cUsed);
1287# ifdef RT_STRICT
1288 RTBIGNUMELEMENT fBorrow = 0;
1289 for (uint32_t i = 0; i < pMinuend->cUsed; i++)
1290 {
1291 RTBIGNUMELEMENT uCorrect = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i], rtBigNumGetElement(pSubtrahend, i), &fBorrow);
1292 AssertMsg(pResult->pauElements[i] == uCorrect, ("[%u]=%#x, expected %#x\n", i, pResult->pauElements[i], uCorrect));
1293 }
1294# endif
1295#else
1296 /*
1297 * The primitive C way.
1298 */
1299 RTBIGNUMELEMENT fBorrow = 0;
1300 for (uint32_t i = 0; i < pMinuend->cUsed; i++)
1301 pResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i],
1302 rtBigNumGetElement(pSubtrahend, i),
1303 &fBorrow);
1304 Assert(fBorrow == 0);
1305#endif
1306
1307 /*
1308 * Trim the result.
1309 */
1310 rtBigNumStripTrailingZeros(pResult);
1311 }
1312 }
1313 /*
1314 * Special case: Subtrahend is zero.
1315 */
1316 else
1317 rc = rtBigNumMagnitudeCopy(pResult, pMinuend);
1318
1319 return rc;
1320}
1321
1322
1323/**
1324 * Substracts a smaller (or equal) magnitude from another one and stores the
1325 * result into the first.
1326 *
1327 * All variables must be unscrambled. The sign flag is not considered nor
1328 * touched. For this reason, the @a pMinuendResult must be larger or equal to
1329 * @a pSubtrahend.
1330 *
1331 * @returns IPRT status code (memory alloc error).
1332 * @param pMinuendResult What to subtract from and return as result.
1333 * @param pSubtrahend What to subtract.
1334 */
1335static int rtBigNumMagnitudeSubThis(PRTBIGNUM pMinuendResult, PCRTBIGNUM pSubtrahend)
1336{
1337 Assert(!pMinuendResult->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
1338 Assert(pMinuendResult != pSubtrahend);
1339 Assert(pMinuendResult->cUsed >= pSubtrahend->cUsed);
1340
1341#ifdef IPRT_BIGINT_WITH_ASM
1342 /*
1343 * Use the assembly worker. Requires same sized element arrays, so zero extend them.
1344 */
1345 int rc = rtBigNumEnsureExtraZeroElements(pMinuendResult, RTBIGNUM_ZERO_ALIGN(pMinuendResult->cUsed));
1346 if (RT_SUCCESS(rc))
1347 rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pSubtrahend, RTBIGNUM_ZERO_ALIGN(pMinuendResult->cUsed));
1348 if (RT_FAILURE(rc))
1349 return rc;
1350 rtBigNumMagnitudeSubThisAssemblyWorker(pMinuendResult->pauElements, pSubtrahend->pauElements, pMinuendResult->cUsed);
1351#else
1352 /*
1353 * The primitive way, as usual.
1354 */
1355 RTBIGNUMELEMENT fBorrow = 0;
1356 for (uint32_t i = 0; i < pMinuendResult->cUsed; i++)
1357 pMinuendResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuendResult->pauElements[i],
1358 rtBigNumGetElement(pSubtrahend, i),
1359 &fBorrow);
1360 Assert(fBorrow == 0);
1361#endif
1362
1363 /*
1364 * Trim the result.
1365 */
1366 rtBigNumStripTrailingZeros(pMinuendResult);
1367
1368 return VINF_SUCCESS;
1369}
1370
1371
1372RTDECL(int) RTBigNumAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
1373{
1374 Assert(pResult != pAugend); Assert(pResult != pAddend);
1375 AssertReturn(pResult->fSensitive >= (pAugend->fSensitive | pAddend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1376
1377 int rc = rtBigNumUnscramble(pResult);
1378 if (RT_SUCCESS(rc))
1379 {
1380 RTBIGNUM_ASSERT_VALID(pResult);
1381 rc = rtBigNumUnscramble((PRTBIGNUM)pAugend);
1382 if (RT_SUCCESS(rc))
1383 {
1384 RTBIGNUM_ASSERT_VALID(pAugend);
1385 rc = rtBigNumUnscramble((PRTBIGNUM)pAddend);
1386 if (RT_SUCCESS(rc))
1387 {
1388 RTBIGNUM_ASSERT_VALID(pAddend);
1389
1390 /*
1391 * Same sign: Add magnitude, keep sign.
1392 * 1 + 1 = 2
1393 * (-1) + (-1) = -2
1394 */
1395 if (pAugend->fNegative == pAddend->fNegative)
1396 {
1397 pResult->fNegative = pAugend->fNegative;
1398 rc = rtBigNumMagnitudeAdd(pResult, pAugend, pAddend);
1399 }
1400 /*
1401 * Different sign: Subtract smaller from larger, keep sign of larger.
1402 * (-5) + 3 = -2
1403 * 5 + (-3) = 2
1404 * (-1) + 3 = 2
1405 * 1 + (-3) = -2
1406 */
1407 else if (rtBigNumMagnitudeCompare(pAugend, pAddend) >= 0)
1408 {
1409 pResult->fNegative = pAugend->fNegative;
1410 rc = rtBigNumMagnitudeSub(pResult, pAugend, pAddend);
1411 if (!pResult->cUsed)
1412 pResult->fNegative = 0;
1413 }
1414 else
1415 {
1416 pResult->fNegative = pAddend->fNegative;
1417 rc = rtBigNumMagnitudeSub(pResult, pAddend, pAugend);
1418 }
1419 rtBigNumScramble((PRTBIGNUM)pAddend);
1420 }
1421 rtBigNumScramble((PRTBIGNUM)pAugend);
1422 }
1423 rtBigNumScramble(pResult);
1424 }
1425 return rc;
1426}
1427
1428
1429RTDECL(int) RTBigNumSubtract(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
1430{
1431 Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
1432 AssertReturn(pResult->fSensitive >= (pMinuend->fSensitive | pSubtrahend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1433
1434 int rc = rtBigNumUnscramble(pResult);
1435 if (RT_SUCCESS(rc))
1436 {
1437 RTBIGNUM_ASSERT_VALID(pResult);
1438 if (pMinuend != pSubtrahend)
1439 {
1440 rc = rtBigNumUnscramble((PRTBIGNUM)pMinuend);
1441 if (RT_SUCCESS(rc))
1442 {
1443 RTBIGNUM_ASSERT_VALID(pMinuend);
1444 rc = rtBigNumUnscramble((PRTBIGNUM)pSubtrahend);
1445 if (RT_SUCCESS(rc))
1446 {
1447 RTBIGNUM_ASSERT_VALID(pSubtrahend);
1448
1449 /*
1450 * Different sign: Add magnitude, keep sign of first.
1451 * 1 - (-2) == 3
1452 * -1 - 2 == -3
1453 */
1454 if (pMinuend->fNegative != pSubtrahend->fNegative)
1455 {
1456 pResult->fNegative = pMinuend->fNegative;
1457 rc = rtBigNumMagnitudeAdd(pResult, pMinuend, pSubtrahend);
1458 }
1459 /*
1460 * Same sign, minuend has greater or equal absolute value: Subtract, keep sign of first.
1461 * 10 - 7 = 3
1462 */
1463 else if (rtBigNumMagnitudeCompare(pMinuend, pSubtrahend) >= 0)
1464 {
1465 pResult->fNegative = pMinuend->fNegative;
1466 rc = rtBigNumMagnitudeSub(pResult, pMinuend, pSubtrahend);
1467 }
1468 /*
1469 * Same sign, subtrahend is larger: Reverse and subtract, invert sign of first.
1470 * 7 - 10 = -3
1471 * -1 - (-3) = 2
1472 */
1473 else
1474 {
1475 pResult->fNegative = !pMinuend->fNegative;
1476 rc = rtBigNumMagnitudeSub(pResult, pSubtrahend, pMinuend);
1477 }
1478 rtBigNumScramble((PRTBIGNUM)pSubtrahend);
1479 }
1480 rtBigNumScramble((PRTBIGNUM)pMinuend);
1481 }
1482 }
1483 else
1484 {
1485 /* zero. */
1486 pResult->fNegative = 0;
1487 rtBigNumSetUsed(pResult, 0);
1488 }
1489 rtBigNumScramble(pResult);
1490 }
1491 return rc;
1492}
1493
1494
1495RTDECL(int) RTBigNumNegateThis(PRTBIGNUM pThis)
1496{
1497 pThis->fNegative = !pThis->fNegative;
1498 return VINF_SUCCESS;
1499}
1500
1501
1502RTDECL(int) RTBigNumNegate(PRTBIGNUM pResult, PCRTBIGNUM pBigNum)
1503{
1504 int rc = RTBigNumAssign(pResult, pBigNum);
1505 if (RT_SUCCESS(rc))
1506 rc = RTBigNumNegateThis(pResult);
1507 return rc;
1508}
1509
1510
1511/**
1512 * Multiplies the magnitudes of two values, letting the caller care about the
1513 * sign bit.
1514 *
1515 * @returns IPRT status code.
1516 * @param pResult Where to store the result.
1517 * @param pMultiplicand The first value.
1518 * @param pMultiplier The second value.
1519 */
1520static int rtBigNumMagnitudeMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
1521{
1522 Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
1523 Assert(!pResult->fCurScrambled); Assert(!pMultiplicand->fCurScrambled); Assert(!pMultiplier->fCurScrambled);
1524
1525 /*
1526 * Multiplication involving zero is zero.
1527 */
1528 if (!pMultiplicand->cUsed || !pMultiplier->cUsed)
1529 {
1530 pResult->fNegative = 0;
1531 rtBigNumSetUsed(pResult, 0);
1532 return VINF_SUCCESS;
1533 }
1534
1535 /*
1536 * Allocate a result array that is the sum of the two factors, initialize
1537 * it to zero.
1538 */
1539 uint32_t cMax = pMultiplicand->cUsed + pMultiplier->cUsed;
1540 int rc = rtBigNumSetUsed(pResult, cMax);
1541 if (RT_SUCCESS(rc))
1542 {
1543 RT_BZERO(pResult->pauElements, pResult->cUsed * RTBIGNUM_ELEMENT_SIZE);
1544
1545#ifdef IPRT_BIGINT_WITH_ASM
1546 rtBigNumMagnitudeMultiplyAssemblyWorker(pResult->pauElements,
1547 pMultiplier->pauElements, pMultiplier->cUsed,
1548 pMultiplicand->pauElements, pMultiplicand->cUsed);
1549#else
1550 for (uint32_t i = 0; i < pMultiplier->cUsed; i++)
1551 {
1552 RTBIGNUMELEMENT uMultiplier = pMultiplier->pauElements[i];
1553 for (uint32_t j = 0; j < pMultiplicand->cUsed; j++)
1554 {
1555 RTBIGNUMELEMENT uHi;
1556 RTBIGNUMELEMENT uLo;
1557#if RTBIGNUM_ELEMENT_SIZE == 4
1558 uint64_t u64 = ASMMult2xU32RetU64(pMultiplicand->pauElements[j], uMultiplier);
1559 uLo = (uint32_t)u64;
1560 uHi = u64 >> 32;
1561#elif RTBIGNUM_ELEMENT_SIZE == 8
1562 uLo = ASMMult2xU64Ret2xU64(pMultiplicand->pauElements[j], uMultiplier, &uHi);
1563#else
1564# error "Invalid RTBIGNUM_ELEMENT_SIZE value"
1565#endif
1566 RTBIGNUMELEMENT fCarry = 0;
1567 uint64_t k = i + j;
1568 pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uLo, &fCarry);
1569 k++;
1570 pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uHi, &fCarry);
1571 while (fCarry)
1572 {
1573 k++;
1574 pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], 0, &fCarry);
1575 }
1576 Assert(k < cMax);
1577 }
1578 }
1579#endif
1580
1581 /* It's possible we overestimated the output size by 1 element. */
1582 rtBigNumStripTrailingZeros(pResult);
1583 }
1584 return rc;
1585}
1586
1587
1588RTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
1589{
1590 Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
1591 AssertReturn(pResult->fSensitive >= (pMultiplicand->fSensitive | pMultiplier->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1592
1593 int rc = rtBigNumUnscramble(pResult);
1594 if (RT_SUCCESS(rc))
1595 {
1596 RTBIGNUM_ASSERT_VALID(pResult);
1597 rc = rtBigNumUnscramble((PRTBIGNUM)pMultiplicand);
1598 if (RT_SUCCESS(rc))
1599 {
1600 RTBIGNUM_ASSERT_VALID(pMultiplicand);
1601 rc = rtBigNumUnscramble((PRTBIGNUM)pMultiplier);
1602 if (RT_SUCCESS(rc))
1603 {
1604 RTBIGNUM_ASSERT_VALID(pMultiplier);
1605
1606 /*
1607 * The sign values follow XOR rules:
1608 * -1 * 1 = -1; 1 ^ 0 = 1
1609 * 1 * -1 = -1; 1 ^ 0 = 1
1610 * -1 * -1 = 1; 1 ^ 1 = 0
1611 * 1 * 1 = 1; 0 ^ 0 = 0
1612 */
1613 pResult->fNegative = pMultiplicand->fNegative ^ pMultiplier->fNegative;
1614 rc = rtBigNumMagnitudeMultiply(pResult, pMultiplicand, pMultiplier);
1615
1616 rtBigNumScramble((PRTBIGNUM)pMultiplier);
1617 }
1618 rtBigNumScramble((PRTBIGNUM)pMultiplicand);
1619 }
1620 rtBigNumScramble(pResult);
1621 }
1622 return rc;
1623}
1624
1625
1626#if 0 /* unused */
1627/**
1628 * Clears a bit in the magnitude of @a pBigNum.
1629 *
1630 * The variables must be unscrambled.
1631 *
1632 * @param pBigNum The big number.
1633 * @param iBit The bit to clear (0-based).
1634 */
1635DECLINLINE(void) rtBigNumMagnitudeClearBit(PRTBIGNUM pBigNum, uint32_t iBit)
1636{
1637 uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1638 if (iElement < pBigNum->cUsed)
1639 {
1640 iBit &= RTBIGNUM_ELEMENT_BITS - 1;
1641 pBigNum->pauElements[iElement] &= ~RTBIGNUM_ELEMENT_BIT(iBit);
1642 if (iElement + 1 == pBigNum->cUsed && !pBigNum->pauElements[iElement])
1643 rtBigNumStripTrailingZeros(pBigNum);
1644 }
1645}
1646#endif /* unused */
1647
1648
1649/**
1650 * Sets a bit in the magnitude of @a pBigNum.
1651 *
1652 * The variables must be unscrambled.
1653 *
1654 * @returns IPRT status code.
1655 * @param pBigNum The big number.
1656 * @param iBit The bit to clear (0-based).
1657 */
1658DECLINLINE(int) rtBigNumMagnitudeSetBit(PRTBIGNUM pBigNum, uint32_t iBit)
1659{
1660 uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1661 int rc = rtBigNumEnsureElementPresent(pBigNum, iElement);
1662 if (RT_SUCCESS(rc))
1663 {
1664 iBit &= RTBIGNUM_ELEMENT_BITS - 1;
1665 pBigNum->pauElements[iElement] |= RTBIGNUM_ELEMENT_BIT(iBit);
1666 return VINF_SUCCESS;
1667 }
1668 return rc;
1669}
1670
1671
1672#if 0 /* unused */
1673/**
1674 * Writes a bit in the magnitude of @a pBigNum.
1675 *
1676 * The variables must be unscrambled.
1677 *
1678 * @returns IPRT status code.
1679 * @param pBigNum The big number.
1680 * @param iBit The bit to write (0-based).
1681 * @param fValue The bit value.
1682 */
1683DECLINLINE(int) rtBigNumMagnitudeWriteBit(PRTBIGNUM pBigNum, uint32_t iBit, bool fValue)
1684{
1685 if (fValue)
1686 return rtBigNumMagnitudeSetBit(pBigNum, iBit);
1687 rtBigNumMagnitudeClearBit(pBigNum, iBit);
1688 return VINF_SUCCESS;
1689}
1690#endif
1691
1692
1693/**
1694 * Returns the given magnitude bit.
1695 *
1696 * The variables must be unscrambled.
1697 *
1698 * @returns The bit value (1 or 0).
1699 * @param pBigNum The big number.
1700 * @param iBit The bit to return (0-based).
1701 */
1702DECLINLINE(RTBIGNUMELEMENT) rtBigNumMagnitudeGetBit(PCRTBIGNUM pBigNum, uint32_t iBit)
1703{
1704 uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1705 if (iElement < pBigNum->cUsed)
1706 {
1707 iBit &= RTBIGNUM_ELEMENT_BITS - 1;
1708 return (pBigNum->pauElements[iElement] >> iBit) & 1;
1709 }
1710 return 0;
1711}
1712
1713
1714/**
1715 * Shifts the magnitude left by one.
1716 *
1717 * The variables must be unscrambled.
1718 *
1719 * @returns IPRT status code.
1720 * @param pBigNum The big number.
1721 * @param uCarry The value to shift in at the bottom.
1722 */
1723DECLINLINE(int) rtBigNumMagnitudeShiftLeftOne(PRTBIGNUM pBigNum, RTBIGNUMELEMENT uCarry)
1724{
1725 Assert(uCarry <= 1);
1726
1727 /* Do the shifting. */
1728 uint32_t cUsed = pBigNum->cUsed;
1729#ifdef IPRT_BIGINT_WITH_ASM
1730 uCarry = rtBigNumMagnitudeShiftLeftOneAssemblyWorker(pBigNum->pauElements, cUsed, uCarry);
1731#else
1732 for (uint32_t i = 0; i < cUsed; i++)
1733 {
1734 RTBIGNUMELEMENT uTmp = pBigNum->pauElements[i];
1735 pBigNum->pauElements[i] = (uTmp << 1) | uCarry;
1736 uCarry = uTmp >> (RTBIGNUM_ELEMENT_BITS - 1);
1737 }
1738#endif
1739
1740 /* If we still carry a bit, we need to increase the size. */
1741 if (uCarry)
1742 {
1743 int rc = rtBigNumSetUsed(pBigNum, cUsed + 1);
1744 AssertRCReturn(rc, rc);
1745 pBigNum->pauElements[cUsed] = uCarry;
1746 }
1747
1748 return VINF_SUCCESS;
1749}
1750
1751
1752/**
1753 * Shifts the magnitude left by @a cBits.
1754 *
1755 * The variables must be unscrambled.
1756 *
1757 * @returns IPRT status code.
1758 * @param pResult Where to store the result.
1759 * @param pValue The value to shift.
1760 * @param cBits The shift count.
1761 */
1762static int rtBigNumMagnitudeShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
1763{
1764 int rc;
1765 if (cBits)
1766 {
1767 uint32_t cBitsNew = rtBigNumMagnitudeBitWidth(pValue);
1768 if (cBitsNew > 0)
1769 {
1770 if (cBitsNew + cBits > cBitsNew)
1771 {
1772 cBitsNew += cBits;
1773 rc = rtBigNumSetUsedEx(pResult, 0, RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS);
1774 if (RT_SUCCESS(rc))
1775 rc = rtBigNumSetUsed(pResult, RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS);
1776 if (RT_SUCCESS(rc))
1777 {
1778 uint32_t const cLeft = pValue->cUsed;
1779 PCRTBIGNUMELEMENT pauSrc = pValue->pauElements;
1780 PRTBIGNUMELEMENT pauDst = pResult->pauElements;
1781
1782 Assert(ASMMemIsZero(pauDst, (cBits / RTBIGNUM_ELEMENT_BITS) * RTBIGNUM_ELEMENT_SIZE));
1783 pauDst += cBits / RTBIGNUM_ELEMENT_BITS;
1784
1785 cBits &= RTBIGNUM_ELEMENT_BITS - 1;
1786 if (cBits)
1787 {
1788 RTBIGNUMELEMENT uPrev = 0;
1789 for (uint32_t i = 0; i < cLeft; i++)
1790 {
1791 RTBIGNUMELEMENT uCur = pauSrc[i];
1792 pauDst[i] = (uCur << cBits) | (uPrev >> (RTBIGNUM_ELEMENT_BITS - cBits));
1793 uPrev = uCur;
1794 }
1795 uPrev >>= RTBIGNUM_ELEMENT_BITS - cBits;
1796 if (uPrev)
1797 pauDst[pValue->cUsed] = uPrev;
1798 }
1799 else
1800 memcpy(pauDst, pauSrc, cLeft * RTBIGNUM_ELEMENT_SIZE);
1801 }
1802 }
1803 else
1804 rc = VERR_OUT_OF_RANGE;
1805 }
1806 /* Shifting zero always yields a zero result. */
1807 else
1808 rc = rtBigNumSetUsed(pResult, 0);
1809 }
1810 else
1811 rc = rtBigNumMagnitudeCopy(pResult, pValue);
1812 return rc;
1813}
1814
1815
1816RTDECL(int) RTBigNumShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
1817{
1818 Assert(pResult != pValue);
1819 AssertReturn(pResult->fSensitive >= pValue->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
1820
1821 int rc = rtBigNumUnscramble(pResult);
1822 if (RT_SUCCESS(rc))
1823 {
1824 RTBIGNUM_ASSERT_VALID(pResult);
1825 rc = rtBigNumUnscramble((PRTBIGNUM)pValue);
1826 if (RT_SUCCESS(rc))
1827 {
1828 RTBIGNUM_ASSERT_VALID(pValue);
1829
1830 pResult->fNegative = pValue->fNegative;
1831 rc = rtBigNumMagnitudeShiftLeft(pResult, pValue, cBits);
1832
1833 rtBigNumScramble((PRTBIGNUM)pValue);
1834 }
1835 rtBigNumScramble(pResult);
1836 }
1837 return rc;
1838}
1839
1840
1841/**
1842 * Shifts the magnitude right by @a cBits.
1843 *
1844 * The variables must be unscrambled.
1845 *
1846 * @returns IPRT status code.
1847 * @param pResult Where to store the result.
1848 * @param pValue The value to shift.
1849 * @param cBits The shift count.
1850 */
1851static int rtBigNumMagnitudeShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
1852{
1853 int rc;
1854 if (cBits)
1855 {
1856 uint32_t cBitsNew = rtBigNumMagnitudeBitWidth(pValue);
1857 if (cBitsNew > cBits)
1858 {
1859 cBitsNew -= cBits;
1860 uint32_t cElementsNew = RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS;
1861 rc = rtBigNumSetUsed(pResult, cElementsNew);
1862 if (RT_SUCCESS(rc))
1863 {
1864 uint32_t i = cElementsNew;
1865 PCRTBIGNUMELEMENT pauSrc = pValue->pauElements;
1866 PRTBIGNUMELEMENT pauDst = pResult->pauElements;
1867
1868 pauSrc += cBits / RTBIGNUM_ELEMENT_BITS;
1869
1870 cBits &= RTBIGNUM_ELEMENT_BITS - 1;
1871 if (cBits)
1872 {
1873 RTBIGNUMELEMENT uPrev = &pauSrc[i] == &pValue->pauElements[pValue->cUsed] ? 0 : pauSrc[i];
1874 while (i-- > 0)
1875 {
1876 RTBIGNUMELEMENT uCur = pauSrc[i];
1877 pauDst[i] = (uCur >> cBits) | (uPrev << (RTBIGNUM_ELEMENT_BITS - cBits));
1878 uPrev = uCur;
1879 }
1880 }
1881 else
1882 memcpy(pauDst, pauSrc, i * RTBIGNUM_ELEMENT_SIZE);
1883 }
1884 }
1885 else
1886 rc = rtBigNumSetUsed(pResult, 0);
1887 }
1888 else
1889 rc = rtBigNumMagnitudeCopy(pResult, pValue);
1890 return rc;
1891}
1892
1893
1894RTDECL(int) RTBigNumShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
1895{
1896 Assert(pResult != pValue);
1897 AssertReturn(pResult->fSensitive >= pValue->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
1898
1899 int rc = rtBigNumUnscramble(pResult);
1900 if (RT_SUCCESS(rc))
1901 {
1902 RTBIGNUM_ASSERT_VALID(pResult);
1903 rc = rtBigNumUnscramble((PRTBIGNUM)pValue);
1904 if (RT_SUCCESS(rc))
1905 {
1906 RTBIGNUM_ASSERT_VALID(pValue);
1907
1908 pResult->fNegative = pValue->fNegative;
1909 rc = rtBigNumMagnitudeShiftRight(pResult, pValue, cBits);
1910 if (!pResult->cUsed)
1911 pResult->fNegative = 0;
1912
1913 rtBigNumScramble((PRTBIGNUM)pValue);
1914 }
1915 rtBigNumScramble(pResult);
1916 }
1917 return rc;
1918}
1919
1920
1921/**
1922 * Implements the D3 test for Qhat decrementation.
1923 *
1924 * @returns True if Qhat should be decremented.
1925 * @param puQhat Pointer to Qhat.
1926 * @param uRhat The remainder.
1927 * @param uDivisorY The penultimate divisor element.
1928 * @param uDividendJMinus2 The j-2 dividend element.
1929 */
1930DECLINLINE(bool) rtBigNumKnuthD3_ShouldDecrementQhat(RTBIGNUMELEMENT2X const *puQhat, RTBIGNUMELEMENT uRhat,
1931 RTBIGNUMELEMENT uDivisorY, RTBIGNUMELEMENT uDividendJMinus2)
1932{
1933 if (puQhat->s.Lo == RTBIGNUM_ELEMENT_MAX && puQhat->s.Hi == 0)
1934 return true;
1935#if RTBIGNUM_ELEMENT_BITS == 64
1936 RTBIGNUMELEMENT2X TmpLeft;
1937 RTUInt128MulByU64(&TmpLeft, puQhat, uDivisorY);
1938
1939 RTBIGNUMELEMENT2X TmpRight;
1940 TmpRight.s.Lo = 0;
1941 TmpRight.s.Hi = uRhat;
1942 RTUInt128AssignAddU64(&TmpRight, uDividendJMinus2);
1943
1944 if (RTUInt128Compare(&TmpLeft, &TmpRight) > 0)
1945 return true;
1946#else
1947 if (puQhat->u * uDivisorY > ((uint64_t)uRhat << 32) + uDividendJMinus2)
1948 return true;
1949#endif
1950 return false;
1951}
1952
1953
1954/**
1955 * C implementation of the D3 step of Knuth's division algorithm.
1956 *
1957 * This estimates a value Qhat that will be used as quotient "digit" (element)
1958 * at the current level of the division (j).
1959 *
1960 * @returns The Qhat value we've estimated.
1961 * @param pauDividendJN Pointer to the j+n (normalized) dividend element.
1962 * Will access up to two elements prior to this.
1963 * @param uDivZ The last element in the (normalized) divisor.
1964 * @param uDivY The penultimate element in the (normalized) divisor.
1965 */
1966DECLINLINE(RTBIGNUMELEMENT) rtBigNumKnuthD3_EstimateQhat(PCRTBIGNUMELEMENT pauDividendJN,
1967 RTBIGNUMELEMENT uDivZ, RTBIGNUMELEMENT uDivY)
1968{
1969 RTBIGNUMELEMENT2X uQhat;
1970 RTBIGNUMELEMENT uRhat;
1971 RTBIGNUMELEMENT uDividendJN = pauDividendJN[0];
1972 Assert(uDividendJN <= uDivZ);
1973 if (uDividendJN != uDivZ)
1974 rtBigNumElement2xDiv2xBy1x(&uQhat, &uRhat, uDividendJN, pauDividendJN[-1], uDivZ);
1975 else
1976 {
1977 /*
1978 * This is the case where we end up with an initial Qhat that's all Fs.
1979 */
1980 /* Calc the remainder for max Qhat value. */
1981 RTBIGNUMELEMENT2X uTmp1; /* (v[j+n] << bits) + v[J+N-1] */
1982 uTmp1.s.Hi = uDivZ;
1983 uTmp1.s.Lo = pauDividendJN[-1];
1984
1985 RTBIGNUMELEMENT2X uTmp2; /* uQhat * uDividendJN */
1986 uTmp2.s.Hi = uDivZ - 1;
1987 uTmp2.s.Lo = 0 - uDivZ;
1988#if RTBIGNUM_ELEMENT_BITS == 64
1989 RTUInt128AssignSub(&uTmp1, &uTmp2);
1990#else
1991 uTmp1.u -= uTmp2.u;
1992#endif
1993 /* If we overflowed the remainder, don't bother trying to adjust. */
1994 if (uTmp1.s.Hi)
1995 return RTBIGNUM_ELEMENT_MAX;
1996
1997 uRhat = uTmp1.s.Lo;
1998 uQhat.s.Lo = RTBIGNUM_ELEMENT_MAX;
1999 uQhat.s.Hi = 0;
2000 }
2001
2002 /*
2003 * Adjust Q to eliminate all cases where it's two to large and most cases
2004 * where it's one too large.
2005 */
2006 while (rtBigNumKnuthD3_ShouldDecrementQhat(&uQhat, uRhat, uDivY, pauDividendJN[-2]))
2007 {
2008 rtBigNumElement2xDec(&uQhat);
2009 uRhat += uDivZ;
2010 if (uRhat < uDivZ /* overflow */ || uRhat == RTBIGNUM_ELEMENT_MAX)
2011 break;
2012 }
2013
2014 return uQhat.s.Lo;
2015}
2016
2017
2018#ifdef IPRT_BIGINT_WITH_ASM
2019DECLASM(bool) rtBigNumKnuthD4_MulSub(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor,
2020 uint32_t cDivisor, RTBIGNUMELEMENT uQhat);
2021#else
2022/**
2023 * C implementation of the D4 step of Knuth's division algorithm.
2024 *
2025 * This subtracts Divisor * Qhat from the dividend at the current J index.
2026 *
2027 * @returns true if negative result (unlikely), false if positive.
2028 * @param pauDividendJ Pointer to the j-th (normalized) dividend element.
2029 * Will access up to two elements prior to this.
2030 * @param uDivZ The last element in the (normalized) divisor.
2031 * @param uDivY The penultimate element in the (normalized) divisor.
2032 */
2033DECLINLINE(bool) rtBigNumKnuthD4_MulSub(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor,
2034 uint32_t cDivisor, RTBIGNUMELEMENT uQhat)
2035{
2036 uint32_t i;
2037 bool fBorrow = false;
2038 RTBIGNUMELEMENT uMulCarry = 0;
2039 for (i = 0; i < cDivisor; i++)
2040 {
2041 RTBIGNUMELEMENT2X uSub;
2042# if RTBIGNUM_ELEMENT_BITS == 64
2043 RTUInt128MulU64ByU64(&uSub, uQhat, pauDivisor[i]);
2044 RTUInt128AssignAddU64(&uSub, uMulCarry);
2045# else
2046 uSub.u = (uint64_t)uQhat * pauDivisor[i] + uMulCarry;
2047# endif
2048 uMulCarry = uSub.s.Hi;
2049
2050 RTBIGNUMELEMENT uDividendI = pauDividendJ[i];
2051 if (!fBorrow)
2052 {
2053 fBorrow = uDividendI < uSub.s.Lo;
2054 uDividendI -= uSub.s.Lo;
2055 }
2056 else
2057 {
2058 fBorrow = uDividendI <= uSub.s.Lo;
2059 uDividendI -= uSub.s.Lo + 1;
2060 }
2061 pauDividendJ[i] = uDividendI;
2062 }
2063
2064 /* Carry and borrow into the final dividend element. */
2065 RTBIGNUMELEMENT uDividendI = pauDividendJ[i];
2066 if (!fBorrow)
2067 {
2068 fBorrow = uDividendI < uMulCarry;
2069 pauDividendJ[i] = uDividendI - uMulCarry;
2070 }
2071 else
2072 {
2073 fBorrow = uDividendI <= uMulCarry;
2074 pauDividendJ[i] = uDividendI - uMulCarry - 1;
2075 }
2076
2077 return fBorrow;
2078}
2079#endif /* !IPRT_BIGINT_WITH_ASM */
2080
2081
2082/**
2083 * C implementation of the D6 step of Knuth's division algorithm.
2084 *
2085 * This adds the divisor to the dividend to undo the negative value step D4
2086 * produced. This is not very frequent occurence.
2087 *
2088 * @param pauDividendJ Pointer to the j-th (normalized) dividend element.
2089 * Will access up to two elements prior to this.
2090 * @param pauDivisor The last element in the (normalized) divisor.
2091 * @param cDivisor The penultimate element in the (normalized) divisor.
2092 */
2093DECLINLINE(void) rtBigNumKnuthD6_AddBack(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor, uint32_t cDivisor)
2094{
2095 RTBIGNUMELEMENT2X uTmp;
2096 uTmp.s.Lo = 0;
2097
2098 uint32_t i;
2099 for (i = 0; i < cDivisor; i++)
2100 {
2101 uTmp.s.Hi = 0;
2102#if RTBIGNUM_ELEMENT_BITS == 64
2103 RTUInt128AssignAddU64(&uTmp, pauDivisor[i]);
2104 RTUInt128AssignAddU64(&uTmp, pauDividendJ[i]);
2105#else
2106 uTmp.u += pauDivisor[i];
2107 uTmp.u += pauDividendJ[i];
2108#endif
2109 pauDividendJ[i] = uTmp.s.Lo;
2110 uTmp.s.Lo = uTmp.s.Hi;
2111 }
2112
2113 /* The final dividend entry. */
2114 Assert(pauDividendJ[i] + uTmp.s.Lo < uTmp.s.Lo);
2115 pauDividendJ[i] += uTmp.s.Lo;
2116}
2117
2118
2119/**
2120 * Knuth's division (core).
2121 *
2122 * @returns IPRT status code.
2123 * @param pQuotient Where to return the quotient. Can be NULL.
2124 * @param pRemainder Where to return the remainder.
2125 * @param pDividend What to divide.
2126 * @param pDivisor What to divide by.
2127 */
2128static int rtBigNumMagnitudeDivideKnuth(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2129{
2130 Assert(pDivisor->cUsed > 1);
2131 uint32_t const cDivisor = pDivisor->cUsed;
2132 Assert(pDividend->cUsed >= cDivisor);
2133
2134 /*
2135 * Make sure we've got enough space in the quotient, so we can build it
2136 * without any trouble come step D5.
2137 */
2138 int rc;
2139 if (pQuotient)
2140 {
2141 rc = rtBigNumSetUsedEx(pQuotient, 0, pDividend->cUsed - cDivisor + 1);
2142 if (RT_SUCCESS(rc))
2143 rc = rtBigNumSetUsed(pQuotient, pDividend->cUsed - cDivisor + 1);
2144 if (RT_FAILURE(rc))
2145 return rc;
2146 }
2147
2148 /*
2149 * D1. Normalize. The goal here is to make sure the last element in the
2150 * divisor is greater than RTBIGNUMELEMENTS_MAX/2. We must also make sure
2151 * we can access element pDividend->cUsed of the normalized dividend.
2152 */
2153 RTBIGNUM NormDividend;
2154 RTBIGNUM NormDivisor;
2155 PCRTBIGNUM pNormDivisor = &NormDivisor;
2156 rtBigNumInitZeroTemplate(&NormDivisor, pDividend);
2157
2158 uint32_t cNormShift = (RTBIGNUM_ELEMENT_BITS - rtBigNumMagnitudeBitWidth(pDivisor)) & (RTBIGNUM_ELEMENT_BITS - 1);
2159 if (cNormShift)
2160 {
2161 rtBigNumInitZeroTemplate(&NormDividend, pDividend);
2162 rc = rtBigNumMagnitudeShiftLeft(&NormDividend, pDividend, cNormShift);
2163 if (RT_SUCCESS(rc))
2164 rc = rtBigNumMagnitudeShiftLeft(&NormDivisor, pDivisor, cNormShift);
2165 }
2166 else
2167 {
2168 pNormDivisor = pDivisor;
2169 rc = rtBigNumCloneInternal(&NormDividend, pDividend);
2170 }
2171 if (RT_SUCCESS(rc) && pDividend->cUsed == NormDividend.cUsed)
2172 rc = rtBigNumEnsureExtraZeroElements(&NormDividend, NormDividend.cUsed + 1);
2173 if (RT_SUCCESS(rc))
2174 {
2175 /*
2176 * D2. Initialize the j index so we can loop thru the elements in the
2177 * dividend that makes it larger than the divisor.
2178 */
2179 uint32_t j = pDividend->cUsed - cDivisor;
2180
2181 RTBIGNUMELEMENT const DivZ = pNormDivisor->pauElements[cDivisor - 1];
2182 RTBIGNUMELEMENT const DivY = pNormDivisor->pauElements[cDivisor - 2];
2183 for (;;)
2184 {
2185 /*
2186 * D3. Estimate a Q' by dividing the j and j-1 dividen elements by
2187 * the last divisor element, then adjust against the next elements.
2188 */
2189 RTBIGNUMELEMENT uQhat = rtBigNumKnuthD3_EstimateQhat(&NormDividend.pauElements[j + cDivisor], DivZ, DivY);
2190
2191 /*
2192 * D4. Multiply and subtract.
2193 */
2194 bool fNegative = rtBigNumKnuthD4_MulSub(&NormDividend.pauElements[j], pNormDivisor->pauElements, cDivisor, uQhat);
2195
2196 /*
2197 * D5. Test remainder.
2198 * D6. Add back.
2199 */
2200 if (fNegative)
2201 {
2202//__debugbreak();
2203 rtBigNumKnuthD6_AddBack(&NormDividend.pauElements[j], pNormDivisor->pauElements, cDivisor);
2204 uQhat--;
2205 }
2206
2207 if (pQuotient)
2208 pQuotient->pauElements[j] = uQhat;
2209
2210 /*
2211 * D7. Loop on j.
2212 */
2213 if (j == 0)
2214 break;
2215 j--;
2216 }
2217
2218 /*
2219 * D8. Unnormalize the remainder.
2220 */
2221 rtBigNumStripTrailingZeros(&NormDividend);
2222 if (cNormShift)
2223 rc = rtBigNumMagnitudeShiftRight(pRemainder, &NormDividend, cNormShift);
2224 else
2225 rc = rtBigNumMagnitudeCopy(pRemainder, &NormDividend);
2226 if (pQuotient)
2227 rtBigNumStripTrailingZeros(pQuotient);
2228 }
2229
2230 /*
2231 * Delete temporary variables.
2232 */
2233 RTBigNumDestroy(&NormDividend);
2234 if (pDivisor == &NormDivisor)
2235 RTBigNumDestroy(&NormDivisor);
2236 return rc;
2237}
2238
2239
2240static int rtBigNumMagnitudeDivideSlowLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2241{
2242 /*
2243 * Do very simple long division. This ain't fast, but it does the trick.
2244 */
2245 int rc = VINF_SUCCESS;
2246 uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
2247 while (iBit-- > 0)
2248 {
2249 rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
2250 AssertRCBreak(rc);
2251 int iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
2252 if (iDiff >= 0)
2253 {
2254 if (iDiff != 0)
2255 {
2256 rc = rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
2257 AssertRCBreak(rc);
2258 }
2259 else
2260 rtBigNumSetUsed(pRemainder, 0);
2261 rc = rtBigNumMagnitudeSetBit(pQuotient, iBit);
2262 AssertRCBreak(rc);
2263 }
2264 }
2265
2266 /* This shouldn't be necessary. */
2267 rtBigNumStripTrailingZeros(pQuotient);
2268 rtBigNumStripTrailingZeros(pRemainder);
2269
2270 return rc;
2271}
2272
2273
2274/**
2275 * Divides the magnitudes of two values, letting the caller care about the sign
2276 * bit.
2277 *
2278 * All variables must be unscrambled. The sign flag is not considered nor
2279 * touched, this means the caller have to check for zero outputs.
2280 *
2281 * @returns IPRT status code.
2282 * @param pQuotient Where to return the quotient.
2283 * @param pRemainder Where to return the remainder.
2284 * @param pDividend What to divide.
2285 * @param pDivisor What to divide by.
2286 * @param fForceLong Force long division.
2287 */
2288static int rtBigNumMagnitudeDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor,
2289 bool fForceLong)
2290{
2291 Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
2292 Assert(!pQuotient->fCurScrambled); Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
2293
2294 /*
2295 * Just set both output values to zero as that's the return for several
2296 * special case and the initial state of the general case.
2297 */
2298 rtBigNumSetUsed(pQuotient, 0);
2299 rtBigNumSetUsed(pRemainder, 0);
2300
2301 /*
2302 * Dividing something by zero is undefined.
2303 * Diving zero by something is zero, unless the divsor is also zero.
2304 */
2305 if (!pDivisor->cUsed || !pDividend->cUsed)
2306 return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
2307
2308 /*
2309 * Dividing by one? Quotient = dividend, no remainder.
2310 */
2311 if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
2312 return rtBigNumMagnitudeCopy(pQuotient, pDividend);
2313
2314 /*
2315 * Dividend smaller than the divisor. Zero quotient, all divisor.
2316 */
2317 int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
2318 if (iDiff < 0)
2319 return rtBigNumMagnitudeCopy(pRemainder, pDividend);
2320
2321 /*
2322 * Since we already have done the compare, check if the two values are the
2323 * same. The result is 1 and no remainder then.
2324 */
2325 if (iDiff == 0)
2326 {
2327 int rc = rtBigNumSetUsed(pQuotient, 1);
2328 if (RT_SUCCESS(rc))
2329 pQuotient->pauElements[0] = 1;
2330 return rc;
2331 }
2332
2333 /*
2334 * Sort out special cases before going to the preferred or select algorithm.
2335 */
2336 int rc;
2337 if (pDividend->cUsed <= 2 && !fForceLong)
2338 {
2339 if (pDividend->cUsed < 2)
2340 {
2341 /*
2342 * Single element division.
2343 */
2344 RTBIGNUMELEMENT uQ = pDividend->pauElements[0] / pDivisor->pauElements[0];
2345 RTBIGNUMELEMENT uR = pDividend->pauElements[0] % pDivisor->pauElements[0];
2346 rc = VINF_SUCCESS;
2347 if (uQ)
2348 {
2349 rc = rtBigNumSetUsed(pQuotient, 1);
2350 if (RT_SUCCESS(rc))
2351 pQuotient->pauElements[0] = uQ;
2352 }
2353 if (uR && RT_SUCCESS(rc))
2354 {
2355 rc = rtBigNumSetUsed(pRemainder, 1);
2356 if (RT_SUCCESS(rc))
2357 pRemainder->pauElements[0] = uR;
2358 }
2359 }
2360 else
2361 {
2362 /*
2363 * Two elements dividend by a one or two element divisor.
2364 */
2365 RTBIGNUMELEMENT2X uQ, uR;
2366 if (pDivisor->cUsed == 1)
2367 {
2368 rtBigNumElement2xDiv2xBy1x(&uQ, &uR.s.Lo, pDividend->pauElements[1], pDividend->pauElements[0],
2369 pDivisor->pauElements[0]);
2370 uR.s.Hi = 0;
2371 }
2372 else
2373 rtBigNumElement2xDiv(&uQ, &uR, pDividend->pauElements[1], pDividend->pauElements[0],
2374 pDivisor->pauElements[1], pDivisor->pauElements[0]);
2375 rc = rtBigNumElement2xCopyToMagnitude(&uQ, pQuotient);
2376 if (RT_SUCCESS(rc))
2377 rc = rtBigNumElement2xCopyToMagnitude(&uR, pRemainder);
2378 }
2379 }
2380 /*
2381 * Decide upon which algorithm to use. Knuth requires a divisor that's at
2382 * least 2 elements big.
2383 */
2384 else if (pDivisor->cUsed < 2 || fForceLong)
2385 rc = rtBigNumMagnitudeDivideSlowLong(pQuotient, pRemainder, pDividend, pDivisor);
2386 else
2387 rc = rtBigNumMagnitudeDivideKnuth(pQuotient, pRemainder, pDividend, pDivisor);
2388 return rc;
2389}
2390
2391
2392static int rtBigNumDivideCommon(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder,
2393 PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor, bool fForceLong)
2394{
2395 Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
2396 AssertReturn(pQuotient->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
2397 AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
2398
2399 int rc = rtBigNumUnscramble(pQuotient);
2400 if (RT_SUCCESS(rc))
2401 {
2402 RTBIGNUM_ASSERT_VALID(pQuotient);
2403 rc = rtBigNumUnscramble(pRemainder);
2404 if (RT_SUCCESS(rc))
2405 {
2406 RTBIGNUM_ASSERT_VALID(pRemainder);
2407 rc = rtBigNumUnscramble((PRTBIGNUM)pDividend);
2408 if (RT_SUCCESS(rc))
2409 {
2410 RTBIGNUM_ASSERT_VALID(pDividend);
2411 rc = rtBigNumUnscramble((PRTBIGNUM)pDivisor);
2412 if (RT_SUCCESS(rc))
2413 {
2414 RTBIGNUM_ASSERT_VALID(pDivisor);
2415
2416 /*
2417 * The sign value of the remainder is the same as the dividend.
2418 * The sign values of the quotient follow XOR rules, just like multiplication:
2419 * -3 / 2 = -1; r=-1; 1 ^ 0 = 1
2420 * 3 / -2 = -1; r= 1; 1 ^ 0 = 1
2421 * -3 / -2 = 1; r=-1; 1 ^ 1 = 0
2422 * 3 / 2 = 1; r= 1; 0 ^ 0 = 0
2423 */
2424 pQuotient->fNegative = pDividend->fNegative ^ pDivisor->fNegative;
2425 pRemainder->fNegative = pDividend->fNegative;
2426
2427 rc = rtBigNumMagnitudeDivide(pQuotient, pRemainder, pDividend, pDivisor, fForceLong);
2428
2429 if (pQuotient->cUsed == 0)
2430 pQuotient->fNegative = 0;
2431 if (pRemainder->cUsed == 0)
2432 pRemainder->fNegative = 0;
2433
2434 rtBigNumScramble((PRTBIGNUM)pDivisor);
2435 }
2436 rtBigNumScramble((PRTBIGNUM)pDividend);
2437 }
2438 rtBigNumScramble(pRemainder);
2439 }
2440 rtBigNumScramble(pQuotient);
2441 }
2442 return rc;
2443}
2444
2445
2446RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2447{
2448 return rtBigNumDivideCommon(pQuotient, pRemainder, pDividend, pDivisor, false /*fForceLong*/);
2449}
2450
2451
2452RTDECL(int) RTBigNumDivideLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2453{
2454 return rtBigNumDivideCommon(pQuotient, pRemainder, pDividend, pDivisor, true /*fForceLong*/);
2455}
2456
2457
2458/**
2459 * Calculates the modulus of a magnitude value, leaving the sign bit to the
2460 * caller.
2461 *
2462 * All variables must be unscrambled. The sign flag is not considered nor
2463 * touched, this means the caller have to check for zero outputs.
2464 *
2465 * @returns IPRT status code.
2466 * @param pRemainder Where to return the remainder.
2467 * @param pDividend What to divide.
2468 * @param pDivisor What to divide by.
2469 */
2470static int rtBigNumMagnitudeModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2471{
2472 Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
2473 Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
2474
2475 /*
2476 * Just set the output value to zero as that's the return for several
2477 * special case and the initial state of the general case.
2478 */
2479 rtBigNumSetUsed(pRemainder, 0);
2480
2481 /*
2482 * Dividing something by zero is undefined.
2483 * Diving zero by something is zero, unless the divsor is also zero.
2484 */
2485 if (!pDivisor->cUsed || !pDividend->cUsed)
2486 return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
2487
2488 /*
2489 * Dividing by one? Quotient = dividend, no remainder.
2490 */
2491 if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
2492 return VINF_SUCCESS;
2493
2494 /*
2495 * Dividend smaller than the divisor. Zero quotient, all divisor.
2496 */
2497 int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
2498 if (iDiff < 0)
2499 return rtBigNumMagnitudeCopy(pRemainder, pDividend);
2500
2501 /*
2502 * Since we already have done the compare, check if the two values are the
2503 * same. The result is 1 and no remainder then.
2504 */
2505 if (iDiff == 0)
2506 return VINF_SUCCESS;
2507
2508 /** @todo optimize small numbers. */
2509 int rc = VINF_SUCCESS;
2510 if (pDivisor->cUsed < 2)
2511 {
2512 /*
2513 * Do very simple long division. This ain't fast, but it does the trick.
2514 */
2515 uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
2516 while (iBit-- > 0)
2517 {
2518 rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
2519 AssertRCBreak(rc);
2520 iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
2521 if (iDiff >= 0)
2522 {
2523 if (iDiff != 0)
2524 {
2525 rc = rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
2526 AssertRCBreak(rc);
2527 }
2528 else
2529 rtBigNumSetUsed(pRemainder, 0);
2530 }
2531 }
2532 }
2533 else
2534 {
2535 /*
2536 * Join paths with division.
2537 */
2538 rc = rtBigNumMagnitudeDivideKnuth(NULL, pRemainder, pDividend, pDivisor);
2539 }
2540
2541 /* This shouldn't be necessary. */
2542 rtBigNumStripTrailingZeros(pRemainder);
2543 return rc;
2544}
2545
2546
2547RTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2548{
2549 Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
2550 AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
2551
2552 int rc = rtBigNumUnscramble(pRemainder);
2553 if (RT_SUCCESS(rc))
2554 {
2555 RTBIGNUM_ASSERT_VALID(pRemainder);
2556 rc = rtBigNumUnscramble((PRTBIGNUM)pDividend);
2557 if (RT_SUCCESS(rc))
2558 {
2559 RTBIGNUM_ASSERT_VALID(pDividend);
2560 rc = rtBigNumUnscramble((PRTBIGNUM)pDivisor);
2561 if (RT_SUCCESS(rc))
2562 {
2563 RTBIGNUM_ASSERT_VALID(pDivisor);
2564
2565 /*
2566 * The sign value of the remainder is the same as the dividend.
2567 */
2568 pRemainder->fNegative = pDividend->fNegative;
2569
2570 rc = rtBigNumMagnitudeModulo(pRemainder, pDividend, pDivisor);
2571
2572 if (pRemainder->cUsed == 0)
2573 pRemainder->fNegative = 0;
2574
2575 rtBigNumScramble((PRTBIGNUM)pDivisor);
2576 }
2577 rtBigNumScramble((PRTBIGNUM)pDividend);
2578 }
2579 rtBigNumScramble(pRemainder);
2580 }
2581 return rc;
2582}
2583
2584
2585
2586/**
2587 * Exponentiate the magnitude.
2588 *
2589 * All variables must be unscrambled. The sign flag is not considered nor
2590 * touched, this means the caller have to reject negative exponents.
2591 *
2592 * @returns IPRT status code.
2593 * @param pResult Where to return power.
2594 * @param pBase The base value.
2595 * @param pExponent The exponent (assumed positive or zero).
2596 */
2597static int rtBigNumMagnitudeExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
2598{
2599 Assert(pResult != pBase); Assert(pResult != pExponent);
2600 Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled);
2601
2602 /*
2603 * A couple of special cases.
2604 */
2605 int rc;
2606 /* base ^ 0 => 1. */
2607 if (pExponent->cUsed == 0)
2608 {
2609 rc = rtBigNumSetUsed(pResult, 1);
2610 if (RT_SUCCESS(rc))
2611 pResult->pauElements[0] = 1;
2612 return rc;
2613 }
2614
2615 /* base ^ 1 => base. */
2616 if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
2617 return rtBigNumMagnitudeCopy(pResult, pBase);
2618
2619 /*
2620 * Set up.
2621 */
2622 /* Init temporary power-of-two variable to base. */
2623 RTBIGNUM Pow2;
2624 rc = rtBigNumCloneInternal(&Pow2, pBase);
2625 if (RT_SUCCESS(rc))
2626 {
2627 /* Init result to 1. */
2628 rc = rtBigNumSetUsed(pResult, 1);
2629 if (RT_SUCCESS(rc))
2630 {
2631 pResult->pauElements[0] = 1;
2632
2633 /* Make a temporary variable that we can use for temporary storage of the result. */
2634 RTBIGNUM TmpMultiplicand;
2635 rc = rtBigNumCloneInternal(&TmpMultiplicand, pResult);
2636 if (RT_SUCCESS(rc))
2637 {
2638 /*
2639 * Exponentiation by squaring. Reduces the number of
2640 * multiplications to: NumBitsSet(Exponent) + BitWidth(Exponent).
2641 */
2642 uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
2643 uint32_t iBit = 0;
2644 for (;;)
2645 {
2646 if (rtBigNumMagnitudeGetBit(pExponent, iBit) != 0)
2647 {
2648 rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
2649 if (RT_SUCCESS(rc))
2650 rc = rtBigNumMagnitudeMultiply(pResult, &TmpMultiplicand, &Pow2);
2651 if (RT_FAILURE(rc))
2652 break;
2653 }
2654
2655 /* Done? */
2656 iBit++;
2657 if (iBit >= cExpBits)
2658 break;
2659
2660 /* Not done yet, square the base again. */
2661 rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
2662 if (RT_SUCCESS(rc))
2663 rc = rtBigNumMagnitudeMultiply(&Pow2, &TmpMultiplicand, &TmpMultiplicand);
2664 if (RT_FAILURE(rc))
2665 break;
2666 }
2667 }
2668 }
2669 RTBigNumDestroy(&Pow2);
2670 }
2671 return rc;
2672}
2673
2674
2675RTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
2676{
2677 Assert(pResult != pBase); Assert(pResult != pExponent);
2678 AssertReturn(pResult->fSensitive >= (pBase->fSensitive | pExponent->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
2679
2680 int rc = rtBigNumUnscramble(pResult);
2681 if (RT_SUCCESS(rc))
2682 {
2683 RTBIGNUM_ASSERT_VALID(pResult);
2684 rc = rtBigNumUnscramble((PRTBIGNUM)pBase);
2685 if (RT_SUCCESS(rc))
2686 {
2687 RTBIGNUM_ASSERT_VALID(pBase);
2688 rc = rtBigNumUnscramble((PRTBIGNUM)pExponent);
2689 if (RT_SUCCESS(rc))
2690 {
2691 RTBIGNUM_ASSERT_VALID(pExponent);
2692 if (!pExponent->fNegative)
2693 {
2694 pResult->fNegative = pBase->fNegative; /* sign unchanged. */
2695 rc = rtBigNumMagnitudeExponentiate(pResult, pBase, pExponent);
2696 }
2697 else
2698 rc = VERR_BIGNUM_NEGATIVE_EXPONENT;
2699
2700 rtBigNumScramble((PRTBIGNUM)pExponent);
2701 }
2702 rtBigNumScramble((PRTBIGNUM)pBase);
2703 }
2704 rtBigNumScramble(pResult);
2705 }
2706 return rc;
2707}
2708
2709
2710/**
2711 * Modular exponentiation, magnitudes only.
2712 *
2713 * All variables must be unscrambled. The sign flag is not considered nor
2714 * touched, this means the caller have to reject negative exponents and do any
2715 * other necessary sign bit fiddling.
2716 *
2717 * @returns IPRT status code.
2718 * @param pResult Where to return the remainder of the power.
2719 * @param pBase The base value.
2720 * @param pExponent The exponent (assumed positive or zero).
2721 * @param pModulus The modulus value (or divisor if you like).
2722 */
2723static int rtBigNumMagnitudeModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
2724{
2725 Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
2726 Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled); Assert(!pModulus->fCurScrambled);
2727 int rc;
2728
2729 /*
2730 * Check some special cases to get them out of the way.
2731 */
2732 /* Div by 0 => invalid. */
2733 if (pModulus->cUsed == 0)
2734 return VERR_BIGNUM_DIV_BY_ZERO;
2735
2736 /* Div by 1 => no remainder. */
2737 if (pModulus->cUsed == 1 && pModulus->pauElements[0] == 1)
2738 {
2739 rtBigNumSetUsed(pResult, 0);
2740 return VINF_SUCCESS;
2741 }
2742
2743 /* base ^ 0 => 1. */
2744 if (pExponent->cUsed == 0)
2745 {
2746 rc = rtBigNumSetUsed(pResult, 1);
2747 if (RT_SUCCESS(rc))
2748 pResult->pauElements[0] = 1;
2749 return rc;
2750 }
2751
2752 /* base ^ 1 => base. */
2753 if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
2754 return rtBigNumMagnitudeModulo(pResult, pBase, pModulus);
2755
2756 /*
2757 * Set up.
2758 */
2759 /* Result = 1; preallocate space for the result while at it. */
2760 rc = rtBigNumSetUsed(pResult, pModulus->cUsed + 1);
2761 if (RT_SUCCESS(rc))
2762 rc = rtBigNumSetUsed(pResult, 1);
2763 if (RT_SUCCESS(rc))
2764 {
2765 pResult->pauElements[0] = 1;
2766
2767 /* ModBase = pBase or pBase % pModulus depending on the difference in size. */
2768 RTBIGNUM Pow2;
2769 if (pBase->cUsed <= pModulus->cUsed + pModulus->cUsed / 2)
2770 rc = rtBigNumCloneInternal(&Pow2, pBase);
2771 else
2772 rc = rtBigNumMagnitudeModulo(rtBigNumInitZeroTemplate(&Pow2, pBase), pBase, pModulus);
2773
2774 /* Need a couple of temporary variables. */
2775 RTBIGNUM TmpMultiplicand;
2776 rtBigNumInitZeroTemplate(&TmpMultiplicand, pResult);
2777
2778 RTBIGNUM TmpProduct;
2779 rtBigNumInitZeroTemplate(&TmpProduct, pResult);
2780
2781 /*
2782 * We combine the exponentiation by squaring with the fact that:
2783 * (a*b) mod n = ( (a mod n) * (b mod n) ) mod n
2784 *
2785 * Thus, we can reduce the size of intermediate results by mod'ing them
2786 * in each step.
2787 */
2788 uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
2789 uint32_t iBit = 0;
2790 for (;;)
2791 {
2792 if (rtBigNumMagnitudeGetBit(pExponent, iBit) != 0)
2793 {
2794 rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
2795 if (RT_SUCCESS(rc))
2796 rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &Pow2);
2797 if (RT_SUCCESS(rc))
2798 rc = rtBigNumMagnitudeModulo(pResult, &TmpProduct, pModulus);
2799 if (RT_FAILURE(rc))
2800 break;
2801 }
2802
2803 /* Done? */
2804 iBit++;
2805 if (iBit >= cExpBits)
2806 break;
2807
2808 /* Not done yet, square and mod the base again. */
2809 rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
2810 if (RT_SUCCESS(rc))
2811 rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &TmpMultiplicand);
2812 if (RT_SUCCESS(rc))
2813 rc = rtBigNumMagnitudeModulo(&Pow2, &TmpProduct, pModulus);
2814 if (RT_FAILURE(rc))
2815 break;
2816 }
2817
2818 RTBigNumDestroy(&TmpMultiplicand);
2819 RTBigNumDestroy(&TmpProduct);
2820 RTBigNumDestroy(&Pow2);
2821 }
2822 return rc;
2823}
2824
2825
2826RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
2827{
2828 Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
2829 AssertReturn(pResult->fSensitive >= (pBase->fSensitive | pExponent->fSensitive | pModulus->fSensitive),
2830 VERR_BIGNUM_SENSITIVE_INPUT);
2831
2832 int rc = rtBigNumUnscramble(pResult);
2833 if (RT_SUCCESS(rc))
2834 {
2835 RTBIGNUM_ASSERT_VALID(pResult);
2836 rc = rtBigNumUnscramble((PRTBIGNUM)pBase);
2837 if (RT_SUCCESS(rc))
2838 {
2839 RTBIGNUM_ASSERT_VALID(pBase);
2840 rc = rtBigNumUnscramble((PRTBIGNUM)pExponent);
2841 if (RT_SUCCESS(rc))
2842 {
2843 RTBIGNUM_ASSERT_VALID(pExponent);
2844 rc = rtBigNumUnscramble((PRTBIGNUM)pModulus);
2845 if (RT_SUCCESS(rc))
2846 {
2847 RTBIGNUM_ASSERT_VALID(pModulus);
2848 if (!pExponent->fNegative)
2849 {
2850 pResult->fNegative = pModulus->fNegative; /* pBase ^ pExponent / pModulus; result = remainder. */
2851 rc = rtBigNumMagnitudeModExp(pResult, pBase, pExponent, pModulus);
2852 }
2853 else
2854 rc = VERR_BIGNUM_NEGATIVE_EXPONENT;
2855 rtBigNumScramble((PRTBIGNUM)pModulus);
2856 }
2857 rtBigNumScramble((PRTBIGNUM)pExponent);
2858 }
2859 rtBigNumScramble((PRTBIGNUM)pBase);
2860 }
2861 rtBigNumScramble(pResult);
2862 }
2863 return rc;
2864}
2865
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette