diff options
| -rw-r--r-- | BigInt.c | 38 |
1 files changed, 23 insertions, 15 deletions
@@ -382,23 +382,19 @@ B_tostr(MemoryManager *mm, BigInt intx) { return str; } - // TODO: these calculations are based on Wikipedia's statement that - // "4 x ceil(n / 3)" is enough bits of memory. - // This is true, but it grows faster than needed, so from 31 bits onward, - // we use too much memory (adding unnecessary leading 0s). - // The exact value is "ceil(log10(2^x - 1))" + // The exact amount of necessary bcd bits is "ceil(log10(2^x - 1))", + // however this is difficult to compute. + // Wikipedia offers a convenient approximation "4 x ceil(n / 3)", + // which grows faster than the true formula. Simplifying and calculating + // for number of bytes, results in the following formula value. + // Do note, a side effect is that we'll use more memory than needed and + // show unnecessary leading 0s. Later in the code we'll discard these zeroes. usize bcd_bytes = 1 + (n - 1) / 6; - int odd_nibbles = (1 + (n - 1) / 3) % 2; - - char *str; - if (R_Ok != mm->alloc(*mm, (void**)&str, sizeof(char) * (bcd_bytes * 2 - odd_nibbles + 1))) - return NULL; u8 *bcd; - if (R_Ok != mm->alloc(*mm, (void**)&bcd, sizeof(u8) * bcd_bytes)) { - mm->free(*mm, (void**)&str); + if (R_Ok != mm->alloc(*mm, (void**)&bcd, sizeof(u8) * bcd_bytes)) return NULL; - } + memset(bcd, 0, sizeof(u8) * bcd_bytes); UWord mask = (UWord)1 << (UWORD_BIT - 1); @@ -430,12 +426,24 @@ B_tostr(MemoryManager *mm, BigInt intx) { } } + // Remove leading zeroes + while (bcd_bytes > 1 && bcd[bcd_bytes - 1] == 0) + --bcd_bytes; + + int skip_nibble = (bcd[bcd_bytes - 1] & 0b11110000) == 0; + + char *str; + if (R_Ok != mm->alloc(*mm, (void**)&str, sizeof(char) * (bcd_bytes * 2 - skip_nibble + 1))) { + mm->free(*mm, (void**)&bcd); + return NULL; + } + // BCD to char string char *s = str; - if (!odd_nibbles) + if (!skip_nibble) *(s++) = ((bcd[bcd_bytes - 1] & 0b11110000) >> 4) + '0'; - *(s++) = (bcd[bcd_bytes - 1] & 0b00001111) + '0'; + *(s++) = (bcd[bcd_bytes - 1] & 0b00001111) + '0'; for (usize b = bcd_bytes - 2; b < bcd_bytes; --b) { *(s++) = ((bcd[b] & 0b11110000) >> 4) + '0'; |