Arbitrary Base Conversion Algorithm (Javascript)

README.md

Arbitrary Base Conversion Algorithm

This is a function that can convert between arbitrary bases implemented in both Javascript and Python.

Many existing implementations, such as https://rot47.net/base.html or https://gist.github.com/inflammable/2929362 use a number as the internal representation, and thus can't safely encode/decode more than 8 letters of Base64 encoded text, or 9 letters of Base58 text (which isn't enough for parsing a Bitcoin address).

Other implementations rely on complicated third party libraries for bignum (e.g. https://rosettacode.org/wiki/Non-decimal_radices/Convert#JavaScript).

Several implementations required converting to Uint8Arrays (Base 256) as an intermediate. Others were essentially ports of complicated C implementations (see https://github.com/cryptocoinjs/base-x/blob/master/src/index.js).

This implementation works for arbitrary base conversions, such as Binary to Hexadecimal, Octal to Decimal, Binary to Octal, Octal to Hexadecimal, Hexadecimal to Base 36, Ternary to Binary, Ternary to Quadranary, Base 26, Base 32, Base 64, Base 58, Base 57, Base 62, Base 256, Base 512, etc. I believe it should work up until Base 94906265, which should even be enough to encode data into an alphabet consisting of all 1,112,064 valid UTF-8 code points.

Keep in mind that this algorithm is approximately O(n^2*log(srcb)/log(destb)). In practice this isn't noticable until you're processing tens of thousands of digits.

There's additionally an implementation here that uses native ES2020 BigInt, which is still ultimately O(n^2) but for larger strings a bit faster than the standard JS implementation.

base-convert-es2020.js

// arbitrary base conversion function
// By Kevin Kwok ([email protected])
// Released under MIT License in 2021

// This implementation only works on JS engines that have
// native support for BigInt. Consult https://caniuse.com/bigint 
// for more up-to-date information. 

// Requires Edge 2020, Firefox 2019, Chrome 2018, Safari 2021
// or later.

function baseConvertBigInt(digits, srcb, destb){
    let val = 0n
    srcb = BigInt(srcb)
    destb = BigInt(destb)
    for(let i = 0; i < digits.length; i++){
        val = val * srcb + BigInt(digits[i])
    }
    let res = []
    while(val !== 0n){
        res.unshift(Number(val % destb))
        val = val / destb
    }
    return res
}

base-convert.js

// arbitrary base conversion function
// By Kevin Kwok ([email protected])
// Released under MIT License in 2021

function baseConvert(digits, srcb, destb) {
    let start = 0,
        result = []
    while (true) {
        let carry = 0,
            done = true
        for (let i = start; i < digits.length; i++) {
            let p = srcb * carry + digits[i]
            digits[i] = Math.floor(p / destb)
            carry = p % destb
            if (done) {
                if (!digits[i]) start = i
                else done = false
            }
        }
        result.unshift(carry)
        if (done) return result
    }
}

base-convert.py

# arbitrary base conversion function
# By Kevin Kwok ([email protected])
# Released under MIT License in 2021

def baseConvert(digits, srcb, destb):
    start = 0
    result = []
    while True:
        carry = 0
        started = False
        for i in range(start, len(digits)):
            pre = srcb * carry + digits[i]
            divide = pre // destb
            carry = pre % destb
            digits[i] = divide
            if not started:
                if divide == 0:
                    start = i
                else:
                    started = True
        result = [carry] + result
        if not started: break
    return result