base36_128.h

/**
 * base36_128.h - Base-36 encoder-decoder for 128-bit / 25-digit byte array
 *
 * Copyright 2022 LiosK
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy
 * of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
#ifndef BASE36_128_H
#define BASE36_128_H

#include <assert.h>
#include <stdint.h>

#ifdef BASE36_128_USE_NAIVE
/** Converts a digit value array in `src_radix` to that in `dst_radix`. */
int static _base36_128_convert_radix(uint8_t *dst, const uint8_t *src,
                                     int dst_radix, int src_radix, int dst_size,
                                     int src_size) {
  for (int i = 0; i < dst_size; i++) {
    dst[i] = 0;
  }

  for (int i = 0; i < src_size; i++) {
    uint_fast32_t carry = src[i];
    for (int j = dst_size - 1; j >= 0; j--) {
      carry += dst[j] * src_radix;
      dst[j] = carry % dst_radix;
      carry = carry / dst_radix;
    }
    if (carry != 0) {
      return -1; // dst_size too small
    }
  }
  return 0;
}
#else
/** Converts a digit value array in `src_radix` to that in `dst_radix`. */
int static _base36_128_convert_radix(uint8_t *dst, const uint8_t *src,
                                     int dst_radix, int src_radix, int dst_size,
                                     int src_size) {
  for (int i = 0; i < dst_size; i++) {
    dst[i] = 0;
  }

  int dst_used = dst_size - 1;
  uint64_t carry = 0;
  for (int i = 0; i < src_size;) {
    // Reset carry to input (read multiple digits for optimization)
    uint64_t power = 1; // Set to src_radix ^ number of digits read
    while (power < ((uint64_t)1 << 48) && i < src_size) {
      carry = carry * src_radix + src[i++];
      power *= src_radix;
    }

    // Iterate over dst from right while carry != 0 or up to place already used
    int j = dst_size - 1;
    for (; carry > 0 || j >= dst_used; j--) {
      if (j < 0) {
        return -1; // dst_size too small
      }
      carry += dst[j] * power;
      dst[j] = carry % dst_radix;
      carry = carry / dst_radix;
    }
    dst_used = j + 1;
    assert(carry == 0 && dst_used >= 0);
  }
  return 0;
}
#endif /* #ifndef BASE36_128_USE_NAIVE */

#define BASE36_128_LEN (25)

const char BASE36_128_DIGITS[] = "0123456789abcdefghijklmnopqrstuvwxyz";

/** O(1) map from ASCII code points to digit values. */
const uint8_t BASE36_128_DECODE_MAP[256] = {
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10,
    0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c,
    0x1d, 0x1e, 0x1f, 0x20, 0x21, 0x22, 0x23, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14,
    0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
    0x21, 0x22, 0x23, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff};

#ifdef __cplusplus
extern "C" {
#endif

/** Encodes a byte array to text. */
void base36_128_encode(const uint8_t *bytes, char *text) {
  uint8_t dst[BASE36_128_LEN];
  int err = _base36_128_convert_radix(dst, bytes, 36, 256, BASE36_128_LEN, 16);
  assert(err == 0);
  for (int i = 0; i < BASE36_128_LEN; i++) {
    text[i] = BASE36_128_DIGITS[dst[i]];
  }
  text[BASE36_128_LEN] = '\0';
}

/** Decodes text to a byte array. */
int base36_128_decode(const char *text, uint8_t *bytes) {
  uint8_t src[BASE36_128_LEN];
  const uint8_t *uchars = (const uint8_t *)text;
  for (int i = 0; i < BASE36_128_LEN; i++) {
    uint8_t c = BASE36_128_DECODE_MAP[uchars[i]];
    if (c >= 36) {
      return -1; // invalid character
    }
    src[i] = c;
  }
  int err = _base36_128_convert_radix(bytes, src, 256, 36, 16, BASE36_128_LEN);
  assert(err == 0);
  return 0;
}

#ifdef __cplusplus
} /* extern "C" { */
#endif

#endif /* #ifndef BASE36_128_H */