Expose a more straightforward API for base26 encoding

[Artoria2e5]

The current base26 API is constrained by two things: segment length (only exactly 14 and 9) and byte boundary. We have:

const char* base26_triplet_1( const unsigned char *a ); // 0..13
const char* base26_triplet_2( const unsigned char *a ); // 14..27
const char* base26_triplet_3( const unsigned char *a ); // 28..41
const char* base26_triplet_4( const unsigned char *a ); // 42..55
const char* base26_dublet_for_bits_28_to_36( unsigned char *a ); // 28..36
const char* base26_dublet_for_bits_56_to_64( unsigned char *a ); // 56..64

This presents a bit of a problem for downstream users trying to make longer hashes, specifically in RInChi's 17-character key (https://github.com/IUPAC-InChI/RInChI/blob/46643428f8a547114466dc34ab847bfb890b836a/src/lib/rinchi_hashing.cpp#L133-L151)

std::string hash17char(const std::string& input)
{
  unsigned char chksum[32];
  sha2_csum((unsigned char*) input.c_str(), (int) input.length(), chksum);

  std::string result;

  result += base26_triplet_1(chksum);
  result += base26_triplet_2(chksum);
  result += base26_triplet_3(chksum);
  result += base26_triplet_4(chksum);
  result += base26_dublet_for_bits_56_to_64(chksum);
  // chksum[8] = bits 65->...
  result += base26_triplet_1(&chksum[8]);
  return result;
}

The comment says chksum[8] = bits 65->.... This is a lie. We are actually hashing bits 64..77, with bit 64 used twice. (See IUPAC-InChI/RInChI#28.) This is an unfortunate waste of a bit of distinguishing power. It has already happened, but future Keys need not suffer from this if we understand why.

Why did it happen? Can it be better?

To fit the current base26 API. It only provides for consuming byte-aligned data at fixed offsets. Consider instead this Python description of the base26 algorithm:

from itertools import product
from typing import Iterator, Optional
from warnings import warn
from math import ceil
from hashlib import sha256

AZ = [chr(i) for i in range(ord('A'), ord('Z') + 1)]
AAZZ = [''.join(p) for p in product(AZ, repeat=2)]

# Intentially omitted: EXX, TAA-TTV
AAAZZZ = list(filter(lambda s: not (s.startswith('E') or s >= 'TAA' and s <= 'TTV'), (''.join(p) for p in product(AZ, repeat=3))))

def b26(data: bytes, bitlen: Optional[int]) -> Iterator[str]:
    """
    Convert data into InChI segments.

    :param data: The data to convert.
    :param bitlen: The number of bits to consider from the data. If None, use all bits.
    """
    if bitlen is None:
        bitlen = len(data) * 8
    
    d = int.from_bytes(data[:ceil(bitlen/8)], "little")
    while bitlen > 0:
        if bitlen >= 14:
            yield AAAZZZ[d & ((1 << 14) - 1)]
            d >>= 14
            bitlen -= 14
        elif bitlen == 9:
            yield AAZZ[d & ((1 << 9) - 1)]
            d >>= 9
            bitlen -= 9
        else:
            warn(f"No idea what to do with {bitlen} bits left, truncating.")

def b26_14(data: bytes) -> str:
    """Encode 65 bits of data to 14 chars (InChIKey main)."""
    return ''.join(b26(data, 65))

def b26_8(data: bytes) -> str:
    """Encode 37 bits of data to 8 chars (InChIKey minor)."""
    return ''.join(b26(data, 37))

empty_hash = sha256(b"")
print(f"{empty_hash.hexdigest()=}")
print(f"{b26_8(empty_hash.digest())=}")

def key_14(data: str) -> str:
    """Generate a 14-char InChIKey main from the input string."""
    return b26_14(sha256(data.encode()).digest())

# Ethanol: LFQSCWFLJHTTHZ
print(f"{key_14('C2H6O/c1-2-3/h3H,2H2,1H3')=}")

By using Python's native integers which are arbitrary precision ("bigints"), this implementation does not need to care about byte offsets or masks (remember your struggle with FIX_BASE26_ENC_BUG?). It just keeps taking the least significant bits of the hash interpreted as a little-endian.

It would be unreasonable to expect users to compile InChI with a bigint library like GMP. But we don't need a bigint library to do something similar: gcd(14, 8) = 56, which fits in a UINT64. Everything supports UINT64. Therefore consider this expression instead:

typedef uint64_t U64;
U64 take56LE( const char* a ) { return ((U64)a[0]) | ((U64)a[1] << 8) | ((U64)a[2] << 16) | ((U64)a[3] << 24) | ((U64)a[4] << 32) | ((U64)a[5] << 40) | ((U64)a[6] << 48); }
const char* b26_14_3( U64 a, U8 shift ) { return t26[(a >> shift) & ((1 << 14) - 1)]; }
const char* b26_9_2( U64 a, U8 shift ) { return d26[(a >> shift) & ((1 << 9) - 1)]; }

The original API can be implemented as (the caveat being a potential OOB in the first four if len(a) < 7 -- modify take56LE to take a length argument if concerned):

const char* base26_triplet_1( const unsigned char *a ) { return b26_14_3(take56LE(a), 0); }
const char* base26_triplet_2( const unsigned char *a ) { return b26_14_3(take56LE(a), 14); }
const char* base26_triplet_3( const unsigned char *a ) { return b26_14_3(take56LE(a), 28); }
const char* base26_triplet_4( const unsigned char *a ) { return b26_14_3(take56LE(a), 42); }
const char* base26_dublet_for_bits_28_to_36( unsigned char *a ) { return b26_9_2(take56LE(a), 28); }
const char* base26_dublet_for_bits_56_to_64( unsigned char *a ) { return b26_9_2(take56LE(a+7), 0); }

U64 take56LE_safe(const char* a, size_t lena) {
  U64 out = 0;
  U8 len = lena < 7 ? lena : 7;
  for (U8 i = 0; i < len; i++)
    out |= ((U64) a[i] << (i * 8));
  return out;
}

A future maker of bigger hashes may decide to use:

std::string hash17char_new(const std::string& input)
{
  unsigned char chksum[32];
  sha2_csum((unsigned char*) input.c_str(), (int) input.length(), chksum);

  std::string result;
  uint64_t hash56 = take56LE(chksum); // 0..55
  result += b26_14_3(hash56, 0);
  result += b26_14_3(hash56, 14);
  result += b26_14_3(hash56, 28);
  result += b26_14_3(hash56, 42);

  hash56 = take56LE(chksum + 7);
  result += b26_14_3(hash56, 0); // 56..69
  result += b26_9_2(hash56, 14); // 70..78
  return result;
}

There! It's easier to implement for the library (no more endianness woes). It's clear about what it does, which is great for the user. The compiler sees simpler expressions with more common parts to eliminate (sprinkle some inline around). Everyone wins.

Tangentials

• We only consume in chunks of 14 and 9. What's the plan for other sizes? Maybe specify a padding scheme?