urbit-ob

JavaScript utilities for phonemic base wrangling.
Log | Files | Refs | README

commit 97aa737401debe05dcc0f68903790cb56dad7156
parent ea83726505c242d4aff3758b8eb83a6c96d22f6a
Author: Jared Tobin <jared@jtobin.io>
Date:   Sat,  3 Nov 2018 13:15:34 +1300

Merge pull request #14 from urbit/jt-sanitize

Restructure and clean up.
Diffstat:
MCHANGELOG | 9+++++++++
MREADME.md | 73++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
Mpackage-lock.json | 2+-
Mpackage.json | 4++--
Msrc/index.js | 668++-----------------------------------------------------------------------------
Asrc/internal/co.js | 342+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/internal/muk.js | 114+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/internal/ob.js | 139+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Atest/co.test.js | 192+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Dtest/core.test.js | 99-------------------------------------------------------------------------------
Atest/muk.test.js | 21+++++++++++++++++++++
Atest/ob.test.js | 76++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Dtest/property.test.js | 29-----------------------------
Dtest/util.test.js | 51---------------------------------------------------
14 files changed, 967 insertions(+), 852 deletions(-)

diff --git a/CHANGELOG b/CHANGELOG @@ -1,5 +1,14 @@ # Changelog +- 3.0.0 (2018-11-02) + * Major library cleanup and API simplification. Eliminates old, dead, + or redundant code that had accrued over time. Exposes patp, patp2dec, + patp2hex, and hex2patp functions as the API core (and similarly for @q). + * Adds proper in-library documentation, and beefs up the README. + * Adds property tests for both internals and exposed functions. + * Standardises output, e.g. by always including a leading tilde in @p + values. + - 2.0.0 (2018-10-22) * Bundle/distribute as CommonJS. diff --git a/README.md b/README.md @@ -1,16 +1,67 @@ -# ++ ob +# urbit-ob -js implementation of hoon.hoon arm `ob` +[![Build Status](https://secure.travis-ci.org/urbit/ob-js.png)](http://travis-ci.org/urbit/ob-js) +[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT) +[![npm](https://img.shields.io/npm/v/urbit-ob.svg)](https://www.npmjs.com/package/urbit-ob) -This library is responsible for converting urbit addresses from digits to `@p`, -or the phonetic base, that Urbit uses for naming ships. Also works in reverse. +Utilities for phonetic base wrangling. -- `ob.toGalaxyName(0) -> ~zod` -- `ob.toPlanetName(9896704) -> ~poldec-tonteg` -- `ob.toAddress('~marzod') -> 256` +## What -Make sure to `npm install` to install dependencies. Thanks to `keybase.io/aberg` -and `@MDFang` for the following inspiration. +Here you can primarily find functions for dealing with the *phonetic bases* +used by Urbit. The `@p` encoding is used for naming ships, while the `@q` +encoding is used for representing arbitrary data in a memorable and +pronounceable fashion. -- https://github.com/asssaf/urbit-shipyard -- https://github.com/Fang-/urb.lua +The `@p` encoding is an *obfuscated* representation of an underlying 32-bit +number, in particular, hence the 'ob' in the library's name. + +## Install + +A simple `npm install` should do it. + +## Usage + +The library exposes two families of functions: + +* `patp / patp2dec / patp2hex / hex2patp` +* `patq / patq2dec / patq2hex / hex2patq` + +They are pretty self-explanatory. Use `patp` or `patq` to convert base-10 +numbers (or strings encoding base-10 numbers) to `@p` or `@q` respectively. +Use `patp2dec` or `patq2dec` to go in reverse. `patp2hex`, `patq2hex`, and +their inverses work similarly. + +Some examples: + +``` +> const ob = require('urbit-ob') +> ob.patp('0') +'~zod' +> ob.patp2dec('~nidsut-tomdun') +'15663360' +> ob.hex2patq('010203') +'~doznec-binwes' +> ob.patq2hex('~marned-wismul-nilsev-botnyt') +'01ca0e51d20462f3' +``` + +There are a few other noteworthy functions exposed as well: + +* `clan`, for determining the ship class of a `@p` value +* `sein`, for determining the parent of a `@p` value +* `eqPatq`, for comparing `@q` values for equality + +In the third case: `@q` values are considered equal modulo the existence of +leading zero bytes, so that, for example: + +``` +> '~doznec-marzod' === '~nec-marzod' +false +> ob.eqPatq('~doznec-marzod', '~nec-marzod') +true +``` + +## Testing + +A simple `npm test` will run the test suite. diff --git a/package-lock.json b/package-lock.json @@ -1,6 +1,6 @@ { "name": "urbit-ob", - "version": "2.0.0", + "version": "3.0.0", "lockfileVersion": 1, "requires": true, "dependencies": { diff --git a/package.json b/package.json @@ -1,6 +1,6 @@ { "name": "urbit-ob", - "version": "2.0.0", + "version": "3.0.0", "description": "Utilities for Hoon-style atom printing and conversion", "main": "src/index.js", "scripts": { @@ -14,7 +14,7 @@ "urbit" ], "author": "Tlon", - "license": "ISC", + "license": "MIT", "devDependencies": { "chai": "^4.2.0", "jsverify": "^0.8.3", diff --git a/src/index.js b/src/index.js @@ -1,475 +1,6 @@ -const bnjs = require('bn.js') - -const { - isUndefined, - every, - map, - isString, - reduce, - concat, - split, - chunk - } = require('lodash') - -const raku = [ - 3077398253, - 3995603712, - 2243735041, - 1261992695, -] - -const pre = ` -dozmarbinwansamlitsighidfidlissogdirwacsabwissib\ -rigsoldopmodfoglidhopdardorlorhodfolrintogsilmir\ -holpaslacrovlivdalsatlibtabhanticpidtorbolfosdot\ -losdilforpilramtirwintadbicdifrocwidbisdasmidlop\ -rilnardapmolsanlocnovsitnidtipsicropwitnatpanmin\ -ritpodmottamtolsavposnapnopsomfinfonbanmorworsip\ -ronnorbotwicsocwatdolmagpicdavbidbaltimtasmallig\ -sivtagpadsaldivdactansidfabtarmonranniswolmispal\ -lasdismaprabtobrollatlonnodnavfignomnibpagsopral\ -bilhaddocridmocpacravripfaltodtiltinhapmicfanpat\ -taclabmogsimsonpinlomrictapfirhasbosbatpochactid\ -havsaplindibhosdabbitbarracparloddosbortochilmac\ -tomdigfilfasmithobharmighinradmashalraglagfadtop\ -mophabnilnosmilfopfamdatnoldinhatnacrisfotribhoc\ -nimlarfitwalrapsarnalmoslandondanladdovrivbacpol\ -laptalpitnambonrostonfodponsovnocsorlavmatmipfip\ -` - -const suf = ` -zodnecbudwessevpersutletfulpensytdurwepserwylsun\ -rypsyxdyrnuphebpeglupdepdysputlughecryttyvsydnex\ -lunmeplutseppesdelsulpedtemledtulmetwenbynhexfeb\ -pyldulhetmevruttylwydtepbesdexsefwycburderneppur\ -rysrebdennutsubpetrulsynregtydsupsemwynrecmegnet\ -secmulnymtevwebsummutnyxrextebfushepbenmuswyxsym\ -selrucdecwexsyrwetdylmynmesdetbetbeltuxtugmyrpel\ -syptermebsetdutdegtexsurfeltudnuxruxrenwytnubmed\ -lytdusnebrumtynseglyxpunresredfunrevrefmectedrus\ -bexlebduxrynnumpyxrygryxfeptyrtustyclegnemfermer\ -tenlusnussyltecmexpubrymtucfyllepdebbermughuttun\ -bylsudpemdevlurdefbusbeprunmelpexdytbyttyplevmyl\ -wedducfurfexnulluclennerlexrupnedlecrydlydfenwel\ -nydhusrelrudneshesfetdesretdunlernyrsebhulryllud\ -remlysfynwerrycsugnysnyllyndyndemluxfedsedbecmun\ -lyrtesmudnytbyrsenwegfyrmurtelreptegpecnelnevfes\ -` - -// split string at the indicated index -const splitAt = (index, str) => [str.slice(0, index), str.slice(index)]; - -// convert a decimal number to a hex string -const dec2hex = dec => dec.toString(16).padStart(2, '0') - -// groups suffixes into array of syllables -const suffixes = suf.match(/.{1,3}/g) - -// groups prefixes into array of syllables -const prefixes = pre.match(/.{1,3}/g) - -// Get item at an index in array -const getAt = (arr, index) => arr[index] - -// Gets the length of an array -const len = arr => arr.length - -// gets the last index as an int from an array -const lid = arr => arr.length - 1 - -// wraps indexOf -const indexOf = (arr, str) => arr.indexOf(str) - -// is a int odd? -const isOdd = n => n % 2 !== 0 - -// is a int even? -const isEven = n => !isOdd(n) - -// Makes an array of length num populated with its indices -const seq = n => Array.from(Array(n), (x, i) => i) - -// Gets the prefix at an index -const getPrefix = i => getAt(prefixes, i) - -// Gets the suffix at an index -const getSuffix = i => getAt(suffixes, i) - -// Checks if a syllable exists in both suffixes and prefixes -const doesExist = str => [...suffixes, ...prefixes].includes(str) - -// Checks if a suffix exists -const doesSuffixExist = str => suffixes.includes(str) - -// Checks if a prefix exists -const doesPrefixExist = str => prefixes.includes(str) - -// Gets the index of a prefix -const getPrefixIndex = str => indexOf(prefixes, str) - -// Gets the index of a suffix -const getSuffixIndex = str => indexOf(suffixes, str) - -// converts a binary string to a base-10 integer -const bin2dec = str => parseInt(str, 2).toString(10) - -// converts a base-10 integer to a binary string -const dec2bin = num => num.toString(2) - -// converts an @P syllable index to a binary string -const syl2bin = index => dec2bin(index).padStart(8, '0') - -// converts a @P string to an array of syllables -const patp2arr = p => p.replace(/[\^~-]/g,'').match(/.{1,3}/g) - -// converts an array of syllables to a string @P -const arr2patp = a => reduce(a, (acc, syl, i) => isEven(i) - ? i === 0 - ? `~${acc}${syl}` - ? i === 16 - : `${acc}^${syl}` - : `${acc}-${syl}` - : `${acc}${syl}` -, '') - - -const feen = pyn => { - if (pyn >= 0x10000 && pyn <= 0xFFFFFFFF) { - const tmp = fice(pyn - 0x10000) + 0x10000 - return tmp - } - if (pyn >= 0x100000000 && pyn <= 0xffffffffffffffff) { - const f = new bnjs('4294967295') - const g = new bnjs('18446744069414584000') - const lo = pyn.and(f) - const hi = pyn.and(g) - let next = new bnjs(feen(lo)) - return hi.or(next) - } - return pyn -} - - -const fend = cry => { - if (cry >= 0x10000 && cry <= 0xFFFFFFFF) { - const res = new bnjs(teil(cry - 0x10000)) - const resNum = res.add(new bnjs(65536)).toNumber() - return resNum - } - if (cry >= 0x100000000 && cry <= bn(0xffffffffffffffff)) { - const cryBn = new bnjs(cry) - const lo = cryBn.and(new bnjs('0xFFFFFFFF')) - const hi = cryBn.and(new bnjs('0xffffffff00000000')) - const res = hi.or(fend(lo)) - return res.toNumber() - } - return cry -} - - - -const fice = nor => { - let sel = [ - nor % 65535, - nor / 65535 - ] - for (var i = 0; i < 4; i++) { - sel = rynd(i, sel[0], sel[1]) - } - - const res = 65535 * sel[0] + sel[1] - return res -} - - -const teil = vip => { - let sel = [ - vip % 65535, - vip / 65535 - //vip % 0xFFFF, - //vip / 0x10000 - ] - // maybe the for loops got borked in lua conversion - for (var i = 3; i > -1; i--) { - sel = rund(i, sel[0], sel[1]) - } - //var res = bn(bn(0xFFFF).mul(sel[0])).add(sel[1]) - const r1 = new bnjs(65535) - const res = r1.mul(new bnjs(sel[0])).add(new bnjs(sel[1])) - return res.toNumber() -} - - -const rynd = (n, l, r) => { - l = Math.floor(l) - const res = [r, 0] - const m = isEven(n) - ? new bnjs(65535) - : new bnjs(65536) - - //res[1] = (bn(muk(raku[n], 2, r)).add(l)) % m - const r1 = new bnjs(muk(raku[n], 2, r)) - const r2 = r1.add(new bnjs(l)).mod(m) - res[1] = r2.toNumber() - return res -} - - -const rund = (n, l, r) => { - l = Math.floor(l) - const res = [r, 0] - const m = isEven(n) - ? new bnjs(65535) - : new bnjs(65536) - const h = new bnjs(muk(raku[n], 2, r)) - const r1 = new bnjs(m + l) - const r2 = r1.sub(h.mod(m)).mod(m).toString() - res[1] = r2 - return res -} - - -const muk = (syd, len, key) => { - //key = bn(key) - const lo = key & 0xFF - const hi = (key & 0xFF00) / 256 - const res = murmur3(String.fromCharCode(lo) + String.fromCharCode(hi), syd) - return res -} - - -const murmur3 = (data, seed) => { - if (!seed) seed = 0 - - const c1 = new bnjs(3432918353) - const c2 = new bnjs(461845907) - - const f = 4294967295 - - const length = new bnjs(len(data)) - let h1 = new bnjs(seed) - let k1 - const roundedEnd = length & 0xFFFFFFFC - // this will likely need to be redone with bignum - for (var i = 0; i < roundedEnd; i += 4) { - var x = data.charCodeAt(i + 3) ? data.charCodeAt(i + 3) : 0 - k1 = bn(data.charCodeAt(i) & 0xFF) - | ((data.charCodeAt(i + 1) & 0xFF) << 8) - | ((data.charCodeAt(i + 2) & 0xFF) << 16) - | (x << 24) - k1 = k1 * c1 - k1 = (k1 << 15) | ((k1 & 0xFFFFFFFF) >> 17) - k1 = k1 * c2 - h1 = h1 ^ k1 - h1 = (h1 << 13) | ((h1 & 0xFFFFFFFF) >> 19) - h1 = h1 * 5 + 3864292196 - } - - k1 = 0 - const val = length & 0x03 - if (val == 3) { - k1 = (data.charCodeAt(roundedEnd + 2) & 0xFF) << 16 - } - if (val == 3 || val == 2) { - k1 = k1 | (data.charCodeAt(roundedEnd + 1) & 0xFF) << 8 - } - if (val == 3 || val == 2 || val == 1) { - k1 = k1 | (data.charCodeAt(roundedEnd) & 0xFF) - k1 = new bnjs(k1 * c1) - var k2 = new bnjs(k1.and(new bnjs(f)).shrn(17)) - k1 = k1.shln(15).or(k2) - k1 = k1.mul(c2) - h1 = h1.xor(k1) - } - h1 = h1.xor(length) - h1 = h1.xor(h1.and(new bnjs(f)).shrn(16)) - h1 = h1.mul(new bnjs(2246822507)) - h1 = h1.xor(h1.and(new bnjs(f)).shrn(13)) - h1 = h1.mul(new bnjs(3266489909)) - h1 = h1.xor(h1.and(new bnjs(f)).shrn(16)) - return h1.and(new bnjs(f)).toNumber() -} - - -/* - * Public methods - * -- patp2add ( ship name ) - * -- => address number - * -- to{Galaxy,Star,Planet}Ship ( address number ) - * -- => ship name - * ####################### NOT YET IMPLEMENTED ########################## - * -- clan ( ship name or address number (int or bn) ) - * -- => "galaxy", "star", "planet", "moon" or "comet" - * -- sein ( ship name or address number (int or bn) ) - * -- => parent name or address number - * - */ - -const zero = new bnjs(0) -const one = new bnjs(1) -const two = new bnjs(2) -const three = new bnjs(3) -const four = new bnjs(4) -const five = new bnjs(5) - -const clan = (who) => { - const wid = met(three, who) - return wid.lte(one) - ? 'czar' - : wid.eq(two) - ? 'king' - : wid.lte(four) - ? 'duke' - : wid.lte(new bnjs(8)) - ? 'earl' - : 'pawn' -} - -const sein = (who) => { - const mir = clan(who) - const res = - mir === 'czar' - ? who - : mir === 'king' - ? end(three, one, who) - : mir === 'duke' - ? end(four, one, who) - : mir === 'earl' - ? end(five, one, who) - : zero - return add2patp(res) -} - -const bex = (n) => two.pow(n) - -const rsh = (a, b, c) => { - const sub = bex(a).mul(b) - return c.div(bex(sub)) -} - -const met = (a, b, c = zero) => { - return b.eq(zero) - ? c - : met(a, rsh(a, one, b), c.add(one)) -} - -const end = (a, b, c) => c.mod(bex(bex(a).mul(b))) - -const lsh = (a, b, c) => { - const sub = bex(a).mul(b) - return bex(sub).mul(c) -} - -// bignum patp -const patp = (n) => { - let sxz = new bnjs(feen(n)) - let dyy = met(four, sxz) - - let loop = (tsxz, timp, trep) => { - let log = end(four, one, tsxz) - let pre = getPrefix(rsh(three, one, log)) - let suf = getSuffix(end(three, one, log)) - let etc = - (timp.mod(four)).eq(zero) - ? timp.eq(zero) - ? '' - : '--' - : '-' - - let res = pre + suf + etc + trep - - return timp.eq(dyy) - ? trep - : loop(rsh(four, one, tsxz), timp.add(one), res) - } - - let dyx = met(three, sxz) - - return '~' + - (dyx.lte(one) - ? getSuffix(sxz) - : loop(sxz, zero, '')) -} - - - -// bignum patq -const patq = (n) => { - const buff = n.toArrayLike(Buffer) - - const chunked = - isOdd(buff.length) && buff.length > 1 - ? concat([[buff[0]]], chunk(buff.slice(1), 2)) - : chunk(buff, 2) - - const prefixName = byts => - isUndefined(byts[1]) - ? getPrefix(0) + getSuffix(byts[0]) - : getPrefix(byts[0]) + getSuffix(byts[1]) - - const name = byts => - isUndefined(byts[1]) - ? getSuffix(byts[0]) - : getPrefix(byts[0]) + getSuffix(byts[1]) - - // zero-pad odd, >1 bytelength strings for ease of string comparison - const alg = pair => - isOdd(pair.length) && chunked.length > 1 - ? prefixName(pair) - : name(pair) - - return chunked.reduce((acc, elem) => - acc + (acc === '~' ? '' : '-') + alg(elem), '~') -} - - - -/** - * Convert a hex-encoded string to @q. Preserves leading zero bytes. - * @param {string} str a hex-encoded string - * @return {string} a @q-encoded string - */ -const hex2patq = hex => { - const buf = Buffer.from(hex, 'hex') - const chunks = - isOdd(buf.length) - ? concat([[buf[0]]], chunk(buf.slice(1), 2)) - : chunk(buf, 2) - const splat = map(chunks, chunk => - isUndefined(chunk[1]) - ? getPrefix(0) + getSuffix(chunk[0]) - : getPrefix(chunk[0]) + getSuffix(chunk[1]) - ) - return hex.length === 0 - ? '~zod' - : splat.reduce((acc, elem) => - acc + (acc === '~' ? '' : '-') + elem, '~') -} - - - -/** - * Convert a @q-encoded string to hexadecimal. Preserves leading zero bytes. - * @param {string} str a @q-encoded string - * @return {string} a hex-encoded string - */ -const patq2hex = str => { - const chunks = split(str.slice(1), '-') - const splat = map(chunks, chunk => { - let syls = splitAt(3, chunk) - let hex = - syls[1] === '' - ? dec2hex(getSuffixIndex(syls[0])) - : dec2hex(getPrefixIndex(syls[0])) + - dec2hex(getSuffixIndex(syls[1])) - return hex - }) - return str.length === 0 - ? '00' - : splat.join('') -} - +const co = require('./internal/co') +const ob = require('./internal/ob') /** * Remove all leading zero bytes from a hex-encoded string. @@ -481,8 +12,6 @@ const removeLeadingZeroBytes = str => ? removeLeadingZeroBytes(str.slice(2)) : str - - /** * Equality comparison, modulo leading zero bytes. * @param {string} s a hex-encoded string @@ -492,8 +21,6 @@ const removeLeadingZeroBytes = str => const eqModLeadingZeroBytes = (s, t) => removeLeadingZeroBytes(s) === removeLeadingZeroBytes(t) - - /** * Equality comparison on @q values. * @param {string} p a @q-encoded string @@ -501,191 +28,14 @@ const eqModLeadingZeroBytes = (s, t) => * @return {bool} */ const eqPatq = (p, q) => { - const phex = patq2hex(p) - const qhex = patq2hex(q) + const phex = co.patq2hex(p) + const qhex = co.patq2hex(q) return eqModLeadingZeroBytes(phex, qhex) } +module.exports = Object.assign( + co, + ob, + { eqPatq } +) - -// returns the class of a ship from it's name -const tierOfpatp = name => { - const l = len(patp2arr(name)) - if (l <= 1) return 'galaxy' - if (l <= 2) return 'star' - if (l <= 4) return 'planet' - if (l <= 8) return 'moon' - if (l <= 16) return 'comet' - return 'invalid' -} - - -const tierOfadd = addr => { - const b = len(dec2bin(addr)) - if (b <= 8) return 'galaxy' - if (b <= 16) return 'star' - if (b <= 32) return 'planet' - if (b <= 64) return 'moon' - if (b <= 128) return 'comet' - return 'invalid' -} - - -const add2patp = addr => { - const b = len(dec2bin(addr)) - if (b <= 8) return toGalaxyName(addr) - if (b <= 16) return toStarName(addr) - if (b <= 32) return toPlanetName(addr) - if (b <= 64) console.error('Convert to moon not currently supported.') - if (b <= 128) console.error('Convert to comet not currently supported.') - return 'invalid' -} - - -// converts a string @P into an integer address -const patp2add = (name, unscramble) => { - - // set a default true value for unscramble - if (isUndefined(unscramble)) unscramble = true - - // if the name is invalid, return undefined - if (!isValidName(name)) return - - // if the name is a string, convert to array of syllables - if (isString(name)) name = patp2arr(name) - - // concat 8 bit binary numbers of syllable indexes - const addr = reduce(name, (acc, syl, index) => { - return isOdd(index) || len(name) === 1 - ? acc + syl2bin(getSuffixIndex(syl)) - : acc + syl2bin(getPrefixIndex(syl)) - }, '') - - // convert back to base 10 - const addrInt = bin2dec(addr) - - // if unscramble is true, use fend() - return unscramble - ? fend(addrInt) - : addrInt -} - - -// Checks if a string @P is valid -const isValidName = name => { - // convert string @P to array of syllables - const sylArr = patp2arr(name) - - // Quickly fail if length of @p is greater than 1 and odd - if (isOdd(len(sylArr)) && len(sylArr) !== 1) return false - - // check if each syllable exists - const tests = map(sylArr, (syl, index) => isOdd(index) || len(sylArr) === 1 - ? doesSuffixExist(syl) - : doesPrefixExist(syl)) - - // if all syllables exist, return true, if any single syllables don't exist, - // return false - return every(tests, test => test === true) -} - - -// converts a galaxy address to a string @P -const toGalaxyName = galaxy => _add2patp(galaxy, 1) - - -// converts a star address to a string @P -const toStarName = star => _add2patp(star, 2) - - -// converts a planet address to a string @P -const toPlanetName = (scrambled, scramble) => { - if (isUndefined(scramble)) scramble = true - return _add2patp(scrambled, 4, scramble) -} - - -// converts an integer address to a string @P -const _add2patp = (addr, minBytes, scramble) => { - if (isUndefined(scramble)) scramble = true - - if (!minBytes) { - if (addr < 0x100) { - minBytes = 1 - } else if (addr < 0x10000) { - minBytes = 2 - } else { - minBytes = 4 - } - } - - if (minBytes === 4 && scramble) addr = feen(addr) - - const name = reduce(seq(minBytes), (acc, index) => { - const byt = Math.floor(addr % 256) - - addr = addr / 256 - - const syllable = isOdd(index) - ? getPrefix(byt) - : getSuffix(byt) - - return index === 2 - ? acc = syllable + '-' + acc - : acc = syllable + acc - }, '') - - return name -} - -module.exports = { - patp2add: patp2add, - add2patp: add2patp, - - tierOfpatp: tierOfpatp, - tierOfadd: tierOfadd, - - toGalaxyName: toGalaxyName, - toStarName: toStarName, - toPlanetName: toPlanetName, - isValidName: isValidName, - - patp: patp, - patq: patq, - hex2patq: hex2patq, - patq2hex: patq2hex, - eqPatq: eqPatq, - - sein: sein, - _clan: clan, - - _add2patp: _add2patp, - _getsuffix: getSuffix, - _muk: muk, - _feen: feen, - _fend: fend, - _teil: teil, - _getAt: getAt, - _len: len, - _lid: lid, - _indexOf: indexOf, - _isOdd: isOdd, - _isEven: isEven, - _seq: seq, - _getPrefix: getPrefix, - _getSuffix: getSuffix, - _doesExist: doesExist, - _doesSuffixExist: doesSuffixExist, - _doesPrefixExist: doesPrefixExist, - _getPrefixIndex: getPrefixIndex, - _getSuffixIndex: getSuffixIndex, - _bin2dec: bin2dec, - _dec2bin: dec2bin, - _syl2bin: syl2bin, - - _eqModLeadingZeroBytes: eqModLeadingZeroBytes, - - _met: met, - - _arr2patp: arr2patp -} diff --git a/src/internal/co.js b/src/internal/co.js @@ -0,0 +1,342 @@ +// ++ co +// +// See arvo/sys/hoon.hoon. + +const BN = require('bn.js') +const lodash = require('lodash') + +const ob = require('./ob') + +const zero = new BN(0) +const one = new BN(1) +const two = new BN(2) +const three = new BN(3) +const four = new BN(4) +const five = new BN(5) + +const pre = ` +dozmarbinwansamlitsighidfidlissogdirwacsabwissib\ +rigsoldopmodfoglidhopdardorlorhodfolrintogsilmir\ +holpaslacrovlivdalsatlibtabhanticpidtorbolfosdot\ +losdilforpilramtirwintadbicdifrocwidbisdasmidlop\ +rilnardapmolsanlocnovsitnidtipsicropwitnatpanmin\ +ritpodmottamtolsavposnapnopsomfinfonbanmorworsip\ +ronnorbotwicsocwatdolmagpicdavbidbaltimtasmallig\ +sivtagpadsaldivdactansidfabtarmonranniswolmispal\ +lasdismaprabtobrollatlonnodnavfignomnibpagsopral\ +bilhaddocridmocpacravripfaltodtiltinhapmicfanpat\ +taclabmogsimsonpinlomrictapfirhasbosbatpochactid\ +havsaplindibhosdabbitbarracparloddosbortochilmac\ +tomdigfilfasmithobharmighinradmashalraglagfadtop\ +mophabnilnosmilfopfamdatnoldinhatnacrisfotribhoc\ +nimlarfitwalrapsarnalmoslandondanladdovrivbacpol\ +laptalpitnambonrostonfodponsovnocsorlavmatmipfip\ +` + +const suf = ` +zodnecbudwessevpersutletfulpensytdurwepserwylsun\ +rypsyxdyrnuphebpeglupdepdysputlughecryttyvsydnex\ +lunmeplutseppesdelsulpedtemledtulmetwenbynhexfeb\ +pyldulhetmevruttylwydtepbesdexsefwycburderneppur\ +rysrebdennutsubpetrulsynregtydsupsemwynrecmegnet\ +secmulnymtevwebsummutnyxrextebfushepbenmuswyxsym\ +selrucdecwexsyrwetdylmynmesdetbetbeltuxtugmyrpel\ +syptermebsetdutdegtexsurfeltudnuxruxrenwytnubmed\ +lytdusnebrumtynseglyxpunresredfunrevrefmectedrus\ +bexlebduxrynnumpyxrygryxfeptyrtustyclegnemfermer\ +tenlusnussyltecmexpubrymtucfyllepdebbermughuttun\ +bylsudpemdevlurdefbusbeprunmelpexdytbyttyplevmyl\ +wedducfurfexnulluclennerlexrupnedlecrydlydfenwel\ +nydhusrelrudneshesfetdesretdunlernyrsebhulryllud\ +remlysfynwerrycsugnysnyllyndyndemluxfedsedbecmun\ +lyrtesmudnytbyrsenwegfyrmurtelreptegpecnelnevfes\ +` + +const patp2syls = name => + name.replace(/[\^~-]/g,'').match(/.{1,3}/g) + +const splitAt = (index, str) => [str.slice(0, index), str.slice(index)] + +const prefixes = pre.match(/.{1,3}/g) + +const suffixes = suf.match(/.{1,3}/g) + +const bex = (n) => + two.pow(n) + +const lsh = (a, b, c) => + bex(bex(a).mul(b)).mul(c) + +const rsh = (a, b, c) => + c.div(bex(bex(a).mul(b))) + +const met = (a, b, c = zero) => + b.eq(zero) + ? c + : met(a, rsh(a, one, b), c.add(one)) + +const end = (a, b, c) => + c.mod(bex(bex(a).mul(b))) + +/** + * Convert a number to a @p-encoded string. + * + * @param {String, Number, BN} arg + * @return {String} + */ +const patp = (arg) => { + const n = new BN(arg) + + const sxz = ob.feen(n) + const dyy = met(four, sxz) + + const loop = (tsxz, timp, trep) => { + const log = end(four, one, tsxz) + const pre = prefixes[rsh(three, one, log)] + const suf = suffixes[end(three, one, log)] + const etc = + (timp.mod(four)).eq(zero) + ? timp.eq(zero) + ? '' + : '--' + : '-' + + const res = pre + suf + etc + trep + + return timp.eq(dyy) + ? trep + : loop(rsh(four, one, tsxz), timp.add(one), res) + } + + const dyx = met(three, sxz) + + return '~' + + (dyx.lte(one) + ? suffixes[sxz] + : loop(sxz, zero, '')) +} + +/** + * Convert a hex-encoded string to a @p-encoded string. + * + * @param {String} hex + * @return {String} + */ +const hex2patp = (hex) => + patp(new BN(hex, 'hex')) + +/** + * Convert a @p-encoded string to a hex-encoded string. + * + * @param {String} name @p + * @return {String} + */ +const patp2hex = (name) => { + if (isValidPat(name) === false) { + throw new Error('patp2hex: not a valid @p') + } + const syls = patp2syls(name) + + const syl2bin = idx => + idx.toString(2).padStart(8, '0') + + const addr = lodash.reduce(syls, (acc, syl, idx) => + idx % 2 !== 0 || syls.length === 1 + ? acc + syl2bin(suffixes.indexOf(syl)) + : acc + syl2bin(prefixes.indexOf(syl)), + '') + + const bn = new BN(addr, 2) + return ob.fend(bn).toString('hex') +} + +/** + * Convert a @p-encoded string to a bignum. + * + * @param {String} name @p + * @return {BN} + */ +const patp2bn = name => + new BN(patp2hex(name), 'hex') + +/** + * Convert a @p-encoded string to a decimal-encoded string. + * + * @param {String} name @p + * @return {String} + */ +const patp2dec = name => + patp2bn(name).toString() + +/** + * Convert a number to a @q-encoded string. + * + * @param {String, Number, BN} arg + * @return {String} + */ +const patq = (arg) => { + const n = new BN(arg) + + const buf = n.toArrayLike(Buffer) + + const chunked = + buf.length % 2 !== 0 && buf.length > 1 + ? lodash.concat([[buf[0]]], lodash.chunk(buf.slice(1), 2)) + : lodash.chunk(buf, 2) + + const prefixName = byts => + lodash.isUndefined(byts[1]) + ? prefixes[0] + suffixes[byts[0]] + : prefixes[byts[0]] + suffixes[byts[1]] + + const name = byts => + lodash.isUndefined(byts[1]) + ? suffixes[byts[0]] + : prefixes[byts[0]] + suffixes[byts[1]] + + const alg = pair => + pair.length % 2 !== 0 && chunked.length > 1 + ? prefixName(pair) + : name(pair) + + return chunked.reduce((acc, elem) => + acc + (acc === '~' ? '' : '-') + alg(elem), '~') +} + +/** + * Convert a hex-encoded string to a @q-encoded string. + * + * @param {String} hex + * @return {String} + */ +const hex2patq = hex => + patq(new BN(hex, 'hex')) + +/** + * Convert a @q-encoded string to a hex-encoded string. + * + * Note that this preserves leading zero bytes. + * + * @param {String} name @q + * @return {String} + */ +const patq2hex = name => { + if (isValidPat(name) === false) { + throw new Error('patq2hex: not a valid @q') + } + const chunks = lodash.split(name.slice(1), '-') + const dec2hex = dec => + dec.toString(16).padStart(2, '0') + + const splat = lodash.map(chunks, chunk => { + let syls = splitAt(3, chunk) + return syls[1] === '' + ? dec2hex(suffixes.indexOf(syls[0])) + : dec2hex(prefixes.indexOf(syls[0])) + + dec2hex(suffixes.indexOf(syls[1])) + }) + + return name.length === 0 + ? '00' + : splat.join('') +} + +/** + * Convert a @q-encoded string to a bignum. + * + * @param {String} name @q + * @return {BN} + */ +const patq2bn = name => + new BN(patq2hex(name), 'hex') + +/** + * Convert a @q-encoded string to a decimal-encoded string. + * + * @param {String} name @q + * @return {String} + */ +const patq2dec = name => + patq2bn(name).toString() + +/** + * Determine the ship class of a @p value. + * + * @param {String} @p + * @return {String} + */ +const clan = who => { + const name = patp2bn(who) + const wid = met(three, name) + return wid.lte(one) + ? 'galaxy' + : wid.eq(two) + ? 'star' + : wid.lte(four) + ? 'planet' + : wid.lte(new BN(8)) + ? 'moon' + : 'comet' +} + +/** + * Determine the parent of a @p value. + * + * @param {String} @p + * @return {String} + */ +const sein = (name) => { + const mir = clan(name) + const who = patp2bn(name) + const res = + mir === 'galaxy' + ? who + : mir === 'star' + ? end(three, one, who) + : mir === 'planet' + ? end(four, one, who) + : mir === 'moon' + ? end(five, one, who) + : zero + return patp(res) +} + +/** + * Weakly check if a string is a valid @p or @q value. + * + * This is, at present, a pretty weak internal sanity check. It doesn't + * confirm the structure precisely (e.g. dashes), and for @q, it's required + * that q values of (greater than one) odd bytelength have been zero-padded. + * So, for example, '~doznec-binwod' will be considered a valid @q, but + * '~nec-binwod' will not. + * + * @param {String} name a @p or @q value + * @return {String} + */ +const isValidPat = name => { + const syls = patp2syls(name) + + const leadingTilde = name.slice(0, 1) === '~' + const wrongLength = syls.length % 2 !== 0 && syls.length !== 1 + const sylsExist = lodash.reduce(syls, (acc, syl, index) => + acc && + (index % 2 !== 0 || syls.length === 1 + ? suffixes.includes(syl) + : prefixes.includes(syl)), + true) + + return leadingTilde && !wrongLength && sylsExist +} + +module.exports = { + patp, + patp2hex, + patp2dec, + hex2patp, + patq, + patq2hex, + patq2dec, + hex2patq, + clan, + sein +} diff --git a/src/internal/muk.js b/src/internal/muk.js @@ -0,0 +1,114 @@ +// ++ muk +// +// See arvo/sys/hoon.hoon. + +const BN = require('bn.js') + +const ux_FF = new BN(0xFF) +const ux_FF00 = new BN(0xFF00) +const u_256 = new BN(256) + +/** + * Standard murmur3. + * + * @param {Number} syd + * @param {Number} len + * @param {BN} key + * @return {BN} + */ +const muk = (syd, len, key) => { + const lo = key.and(ux_FF).toNumber() + const hi = key.and(ux_FF00).div(u_256).toNumber() + const kee = String.fromCharCode(lo) + String.fromCharCode(hi) + return new BN(murmurhash3_32_gc(kee, syd)) +} + +// see: https://github.com/garycourt/murmurhash-js +// +// Copyright (c) 2011 Gary Court +// +// Permission is hereby granted, free of charge, to any person obtaining a copy of +// this software and associated documentation files (the "Software"), to deal in +// the Software without restriction, including without limitation the rights to +// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +// of the Software, and to permit persons to whom the Software is furnished to do +// so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in all +// copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +// SOFTWARE. + +/** + * JS Implementation of MurmurHash3 (r136) (as of May 20, 2011) + * + * @author <a href="mailto:gary.court@gmail.com">Gary Court</a> + * @see http://github.com/garycourt/murmurhash-js + * @author <a href="mailto:aappleby@gmail.com">Austin Appleby</a> + * @see http://sites.google.com/site/murmurhash/ + * + * @param {string} key ASCII only + * @param {number} seed Positive integer only + * @return {number} 32-bit positive integer hash + **/ +const murmurhash3_32_gc = (key, seed) => { + let remainder, bytes, h1, h1b, c1, c1b, c2, c2b, k1, i; + + remainder = key.length & 3; // key.length % 4 + bytes = key.length - remainder; + h1 = seed; + c1 = 0xcc9e2d51; + c2 = 0x1b873593; + i = 0; + + while (i < bytes) { + k1 = + ((key.charCodeAt(i) & 0xff)) | + ((key.charCodeAt(++i) & 0xff) << 8) | + ((key.charCodeAt(++i) & 0xff) << 16) | + ((key.charCodeAt(++i) & 0xff) << 24); + ++i; + + k1 = ((((k1 & 0xffff) * c1) + ((((k1 >>> 16) * c1) & 0xffff) << 16))) & 0xffffffff; + k1 = (k1 << 15) | (k1 >>> 17); + k1 = ((((k1 & 0xffff) * c2) + ((((k1 >>> 16) * c2) & 0xffff) << 16))) & 0xffffffff; + + h1 ^= k1; + h1 = (h1 << 13) | (h1 >>> 19); + h1b = ((((h1 & 0xffff) * 5) + ((((h1 >>> 16) * 5) & 0xffff) << 16))) & 0xffffffff; + h1 = (((h1b & 0xffff) + 0x6b64) + ((((h1b >>> 16) + 0xe654) & 0xffff) << 16)); + } + + k1 = 0; + + switch (remainder) { + case 3: k1 ^= (key.charCodeAt(i + 2) & 0xff) << 16; + case 2: k1 ^= (key.charCodeAt(i + 1) & 0xff) << 8; + case 1: k1 ^= (key.charCodeAt(i) & 0xff); + + k1 = (((k1 & 0xffff) * c1) + ((((k1 >>> 16) * c1) & 0xffff) << 16)) & 0xffffffff; + k1 = (k1 << 15) | (k1 >>> 17); + k1 = (((k1 & 0xffff) * c2) + ((((k1 >>> 16) * c2) & 0xffff) << 16)) & 0xffffffff; + h1 ^= k1; + } + + h1 ^= key.length; + + h1 ^= h1 >>> 16; + h1 = (((h1 & 0xffff) * 0x85ebca6b) + ((((h1 >>> 16) * 0x85ebca6b) & 0xffff) << 16)) & 0xffffffff; + h1 ^= h1 >>> 13; + h1 = ((((h1 & 0xffff) * 0xc2b2ae35) + ((((h1 >>> 16) * 0xc2b2ae35) & 0xffff) << 16))) & 0xffffffff; + h1 ^= h1 >>> 16; + + return h1 >>> 0; +} + +module.exports = { + muk +} diff --git a/src/internal/ob.js b/src/internal/ob.js @@ -0,0 +1,139 @@ +// ++ ob +// +// See arvo/sys/hoon.hoon. + +const BN = require('bn.js') +const { muk } = require('./muk') + +const ux_1_0000 = new BN('10000', 'hex') +const ux_ffff_ffff = new BN('ffffffff', 'hex') +const ux_1_0000_0000 = new BN('100000000', 'hex') +const ux_ffff_ffff_ffff_ffff = new BN('ffffffffffffffff', 'hex') +const ux_ffff_ffff_0000_0000 = new BN('ffffffff00000000', 'hex') + +const u_65535 = new BN('65535') +const u_65536 = new BN('65536') + +/** + * Conceal structure v2. + * + * @param {String, Number, BN} pyn + * @return {BN} + */ +const feen = (arg) => { + const loop = (pyn) => { + const lo = pyn.and(ux_ffff_ffff) + const hi = pyn.and(ux_ffff_ffff_0000_0000) + + return pyn.gte(ux_1_0000) && pyn.lte(ux_ffff_ffff) + ? ux_1_0000.add(fice(pyn.sub(ux_1_0000))) + : pyn.gte(ux_1_0000_0000) && pyn.lte(ux_ffff_ffff_ffff_ffff) + ? hi.or(loop(lo)) + : pyn + } + + return loop(new BN(arg)) +} + +/** + * Restore structure v2. + * + * @param {String, Number, BN} pyn + * @return {BN} + */ +const fend = (arg) => { + const loop = (cry) => { + const lo = cry.and(ux_ffff_ffff) + const hi = cry.and(ux_ffff_ffff_0000_0000) + + return cry.gte(ux_1_0000) && cry.lte(ux_ffff_ffff) + ? ux_1_0000.add(teil(cry.sub(ux_1_0000))) + : cry.gte(ux_1_0000_0000) && cry.lte(ux_ffff_ffff_ffff_ffff) + ? hi.or(loop(lo)) + : cry + } + + return loop(new BN(arg)) +} + +/** + * Adapted from Black and Rogaway "Ciphers with arbitrary finite domains", + * 2002. + * + * @param {String, Number, BN} + * @return {BN} + */ +const fice = (arg) => { + const nor = new BN(arg) + + const sel = + rynd(3, + rynd(2, + rynd(1, + rynd(0, [ nor.mod(u_65535), nor.div(u_65535) ])))) + + return (u_65535.mul(sel[0])).add(sel[1]) +} + +/** + * Reverse fice. + * + * @param {String} vip + * @return {BN} + */ +const teil = (arg) => { + const vip = new BN(arg) + + const sel = + rund(0, + rund(1, + rund(2, + rund(3, [ vip.mod(u_65535), vip.div(u_65535) ])))) + + return (u_65535.mul(sel[0])).add(sel[1]) +} + +/** + * Feistel round. + * + * @param {Number} n + * @param {Array<BN>} [l, r] + * @return {Array<BN>} + */ +const rynd = (n, arr) => { + const l = arr[0] + const r = arr[1] + const p = n % 2 === 0 ? u_65535 : u_65536 + return [ r, l.add(muk(raku[n], 2, r)).mod(p) ] +} + +/** + * Reverse round. + * + * @param {Number} n + * @param {Array<BN>} [l, r] + * @return {Array<BN>} + */ +const rund = (n, arr) => { + const l = arr[0] + const r = arr[1] + const p = n % 2 === 0 ? u_65535 : u_65536 + return [ r, l.add(p).sub(muk(raku[n], 2, r).mod(p)).mod(p) ] +} + +const raku = [ + 0xb76d5eed, + 0xee281300, + 0x85bcae01, + 0x4b387af7, +] + +module.exports = { + feen, + fend, + fice, + teil, + rynd, + rund, + raku +} diff --git a/test/co.test.js b/test/co.test.js @@ -0,0 +1,192 @@ +const BN = require('bn.js') +const { expect } = require('chai'); +const jsc = require('jsverify') +const { + patp, + patp2hex, + patp2dec, + hex2patp, + patq, + patq2hex, + patq2dec, + hex2patq, + clan, + sein + } = require('../src/internal/co') + +const patps = jsc.uint32.smap( + num => patp(num), + pp => parseInt(patp2dec(pp)) +) + +const patqs = jsc.uint32.smap( + num => patq(num), + pq => parseInt(patq2dec(pq)) +) + +describe('patp, etc.', () => { + it('patp2dec matches expected reference values', () => { + expect(patp2dec('~zod')).to.equal('0') + expect(patp2dec('~lex')).to.equal('200') + expect(patp2dec('~binzod')).to.equal('512') + expect(patp2dec('~samzod')).to.equal('1024') + expect(patp2dec('~poldec-tonteg')).to.equal('9896704') + expect(patp2dec('~nidsut-tomdun')).to.equal('15663360') + }) + + it('patp matches expected reference values', () => { + expect(patp('0')).to.equal('~zod') + expect(patp('200')).to.equal('~lex') + expect(patp('512')).to.equal('~binzod') + expect(patp('1024')).to.equal('~samzod') + expect(patp('9896704')).to.equal('~poldec-tonteg') + expect(patp('15663360')).to.equal('~nidsut-tomdun') + }) + + it('large patp values match expected reference values', () => { + expect(hex2patp('7468697320697320736f6d6520766572792068696768207175616c69747920656e74726f7079')) + .to.equal('~divmes-davset-holdet--sallun-salpel-taswet-holtex--watmeb-tarlun-picdet-magmes--holter-dacruc-timdet-divtud--holwet-maldut-padpel-sivtud') + }) + + it('patp2hex throws on invalid patp', () => { + let input = () => patp2hex('nidsut-tomdun') + expect(input).to.throw() + input = () => patp2hex('~nidsut-tomdzn') + expect(input).to.throw() + input = () => patp2hex('~sut-tomdun') + expect(input).to.throw() + input = () => patp2hex('~nidsut-dun') + expect(input).to.throw() + }) + + it('patp and patp2dec are inverses', () => { + let iso0 = jsc.forall(jsc.uint32, num => + parseInt(patp2dec(patp(num))) === num + ) + + let iso1 = jsc.forall(patps, pp => + patp(patp2dec(pp)) === pp + ) + + jsc.assert(iso0) + jsc.assert(iso1) + }) + + it('patp2hex and hex2patp are inverses', () => { + let iso0 = jsc.forall(jsc.uint32, num => + parseInt(patp2hex(hex2patp(num.toString(16))), 16) === num + ) + + let iso1 = jsc.forall(patps, pp => + hex2patp(patp2hex(pp)) === pp + ) + + jsc.assert(iso0) + jsc.assert(iso1) + }) +}) + +describe('patq, etc.', () => { + it('patq2dec matches expected reference values', () => { + expect(patq2dec('~zod')).to.equal('0') + expect(patq2dec('~binzod')).to.equal('512') + expect(patq2dec('~samzod')).to.equal('1024') + expect(patq2dec('~poldec-tonteg')).to.equal('4016240379') + expect(patq2dec('~nidsut-tomdun')).to.equal('1208402137') + }) + + it('patq matches expected reference values', () => { + expect(patq('0')).to.equal('~zod') + expect(patq('512')).to.equal('~binzod') + expect(patq('1024')).to.equal('~samzod') + expect(patq('4016240379')).to.equal('~poldec-tonteg') + expect(patq('1208402137')).to.equal('~nidsut-tomdun') + }) + + it('large patq values match expected reference values', () => { + expect(hex2patq('01010101010101010102')).to.equal('~marnec-marnec-marnec-marnec-marbud') + expect(hex2patq('6d7920617765736f6d65207572626974207469636b65742c206920616d20736f206c75636b79')) + .to.equal('~tastud-holruc-sidwet-salpel-taswet-holdeg-paddec-davdut-holdut-davwex-balwet-divwen-holdet-holruc-taslun-salpel-holtux-dacwex-baltud') + }) + + it('patq2hex throws on invalid patp', () => { + let input = () => patq2hex('nidsut-tomdun') + expect(input).to.throw() + input = () => patq2hex('~nidsut-tomdzn') + expect(input).to.throw() + input = () => patq2hex('~sut-tomdun') + expect(input).to.throw() + input = () => patq2hex('~nidsut-dun') + expect(input).to.throw() + }) + + it('patq and patq2dec are inverses', () => { + let iso0 = jsc.forall(jsc.uint32, num => + parseInt(patq2dec(patq(num))) === num + ) + + let iso1 = jsc.forall(patqs, pp => + patq(patq2dec(pp)) === pp + ) + + jsc.assert(iso0) + jsc.assert(iso1) + }) + + it('patq2hex and hex2patq are inverses', () => { + let iso0 = jsc.forall(jsc.uint32, num => + parseInt(patq2hex(hex2patq(num.toString(16))), 16) === num + ) + + let iso1 = jsc.forall(patqs, pp => + hex2patq(patq2hex(pp)) === pp + ) + + jsc.assert(iso0) + jsc.assert(iso1) + }) +}) + +describe('clan/sein', () => { + it('clan works as expected', () => { + expect(clan('~zod')).to.equal('galaxy') + expect(clan('~fes')).to.equal('galaxy') + expect(clan('~marzod')).to.equal('star') + expect(clan('~fassec')).to.equal('star') + expect(clan('~dacsem-fipwex')).to.equal('planet') + expect(clan('~fidnum-rosbyt')).to.equal('planet') + expect(clan('~doznec-bannux-nopfen')).to.equal('moon') + expect(clan('~dozryt--wolmep-racmyl-padpeg-mocryp')).to.equal('comet') + }) + + it('clan throws on invalid input', () => { + let input = () => clan('~zord') + expect(input).to.throw() + input = () => clan('zod') + expect(input).to.throw() + input = () => clan('~nid-tomdun') + expect(input).to.throw() + }) + + it('sein works as expected', () => { + expect(sein('~zod')).to.equal('~zod') + expect(sein('~nec')).to.equal('~nec') + expect(sein('~rep')).to.equal('~rep') + expect(sein('~marzod')).to.equal('~zod') + expect(sein('~marnec')).to.equal('~nec') + expect(sein('~fassec')).to.equal('~sec') + expect(sein('~nidsut-tomdun')).to.equal('~marzod') + expect(sein('~sansym-ribnux')).to.equal('~marnec') + }) + + it('sein throws on invalid input', () => { + let input = () => sein('~zord') + expect(input).to.throw() + input = () => sein('zod') + expect(input).to.throw() + input = () => sein('~nid-tomdun') + expect(input).to.throw() + }) + +}) + diff --git a/test/core.test.js b/test/core.test.js @@ -1,99 +0,0 @@ -const expect = require('chai').expect; -const bnjs = require('bn.js'); -const ob = require('../src'); - -describe('patp2add/add2patp', () => { - it('patp2add', () => { - expect(ob.patp2add('lex')).to.equal('200'); - expect(ob.patp2add('samzod')).to.equal('1024'); - expect(ob.patp2add('sambinzod')).to.equal(undefined); - expect(ob.patp2add('poldec-tonteg')).to.equal(9896704) - }) - - it('add2patp', () => { - expect(ob.add2patp(0, 1, false)).to.equal('zod'); - expect(ob.add2patp(512, 2, false)).to.equal('binzod'); - expect(ob.add2patp(9896704, 4, true)).to.equal('poldec-tonteg'); - expect(ob.add2patp(0)).to.equal('zod'); - expect(ob.add2patp(512)).to.equal('binzod'); - expect(ob.add2patp(9896704)).to.equal('poldec-tonteg'); - }) -}) - -describe('name functions', () => { - it('toGalaxyName/toStarName/toPlanetName', () => { - expect(ob.toGalaxyName(200)).to.equal('lex'); - expect(ob.toStarName(512)).to.equal('binzod'); - expect(ob.toPlanetName(9896704)).to.equal('poldec-tonteg'); - }) - - it('isValidName', () => { - expect(ob.isValidName('poldec-tonteg')).to.equal(true); - expect(ob.isValidName('aaa')).to.equal(false); - expect(ob.isValidName('aaaaaa')).to.equal(false); - expect(ob.isValidName('//////')).to.equal(false); - expect(ob.isValidName('////////////')).to.equal(false); - expect(ob.isValidName('//////-//////')).to.equal(false); - }) -}) - -describe('tiers', () => { - it('tierOfPatp', () => { - expect(ob.tierOfpatp('poldec-tonteg')).to.equal('planet'); - expect(ob.tierOfpatp('poldec')).to.equal('star'); - expect(ob.tierOfpatp('zod')).to.equal('galaxy'); - expect(ob.tierOfpatp('binzod')).to.equal('star'); - expect(ob.tierOfpatp('poldec-tonteg')).to.equal('planet'); - }) - - it('tierOfadd', () => { - expect(ob.tierOfadd(0)).to.equal('galaxy'); - expect(ob.tierOfadd(512)).to.equal('star'); - expect(ob.tierOfadd(9896704)).to.equal('planet'); - }) -}) - -describe('@p/@q encodings', () => { - it('@p', () => { - expect(ob.patp('0')).to.equal('~zod'); - expect(ob.patp('4294967295')).to.equal('~dostec-risfen'); - expect(ob.patp('328256967394537077627')).to.equal('~dozsyx--halrux-samlep-posmus-ranrux'); - - let input = new bnjs('7468697320697320736f6d6520766572792068696768207175616c69747920656e74726f7079', 16); - let expected = '~divmes-davset-holdet--sallun-salpel-taswet-holtex--watmeb-tarlun-picdet-magmes--holter-dacruc-timdet-divtud--holwet-maldut-padpel-sivtud'; - expect(ob.patp(input)).to.equal(expected); - }) - - it('@q', () => { - expect(ob.patq(new bnjs('0'))).to.equal('~zod'); - expect(ob.patq(new bnjs('0102', 'hex'))).to.equal('~marbud'); - expect(ob.patq(new bnjs('010102', 'hex'))).to.equal('~doznec-marbud'); - expect(ob.patq(new bnjs('01010101010101010102', 'hex'))).to.equal('~marnec-marnec-marnec-marnec-marbud'); - expect(ob.patq(new bnjs('6d7920617765736f6d65207572626974207469636b65742c206920616d20736f206c75636b79', 'hex'))).to.equal('~tastud-holruc-sidwet-salpel-taswet-holdeg-paddec-davdut-holdut-davwex-balwet-divwen-holdet-holruc-taslun-salpel-holtux-dacwex-baltud'); - }) -}) - -describe('clan/sein', () => { - it('clan works as expected', () => { - expect(ob._clan(new bnjs(0))).to.equal('czar'); - expect(ob._clan(new bnjs(255))).to.equal('czar'); - expect(ob._clan(new bnjs(256))).to.equal('king'); - expect(ob._clan(new bnjs(50000))).to.equal('king'); - expect(ob._clan(new bnjs(70000))).to.equal('duke'); - expect(ob._clan(new bnjs(2170000))).to.equal('duke'); - expect(ob._clan(new bnjs('5232170000'))).to.equal('earl'); - expect(ob._clan(new bnjs('525525525125232170000'))).to.equal('pawn'); - }) - - it('sein works as expected', () => { - expect(ob.sein(new bnjs(0))).to.equal('zod'); - expect(ob.sein(new bnjs(1))).to.equal('nec'); - expect(ob.sein(new bnjs(250))).to.equal('rep'); - expect(ob.sein(new bnjs(256))).to.equal('zod'); - expect(ob.sein(new bnjs(257))).to.equal('nec'); - expect(ob.sein(new bnjs(50000))).to.equal('sec'); - expect(ob.sein(new bnjs(15663360))).to.equal('marzod'); - expect(ob.sein(new bnjs(15663361))).to.equal('marnec'); - }) -}) - diff --git a/test/muk.test.js b/test/muk.test.js @@ -0,0 +1,21 @@ +const BN = require('bn.js') +const { expect } = require('chai'); +const { isEqual } = require('lodash') +const { muk } = require('../src/internal/muk') + +describe('muk', () => { + it('matches expected reference values', () => { + let input = new BN(0x101) + let output = new BN(0x42081a9b) + expect(muk(0, 2, input).eq(output)).to.equal(true) + + input = new BN(0x201) + output = new BN(0x64c7667e) + expect(muk(0, 2, input).eq(output)).to.equal(true) + + input = new BN(0x4812) + output = new BN(0xa30782dc) + expect(muk(0, 2, input).eq(output)).to.equal(true) + }) +}) + diff --git a/test/ob.test.js b/test/ob.test.js @@ -0,0 +1,76 @@ +const BN = require('bn.js') +const { expect } = require('chai'); +const jsc = require('jsverify') +const { isEqual } = require('lodash') +const { + feen, + fend, + fice, + teil, + rynd, + rund + } = require('../src/internal/ob') + +const bignums = jsc.uint32.smap( + (num) => new BN(num), + (bn) => bn.toNumber() +) + +describe('feen/fend', () => { + it('feen and fend are inverses', () => { + let prop = jsc.forall(bignums, bn => + fend(feen(bn)).eq(bn) && feen(fend(bn)).eq(bn)) + + jsc.assert(prop) + }) + + it('feen matches expected reference values', () => { + let input = new BN('123456789') + let output = new BN('1897766331') + expect(feen(input).eq(output)).to.equal(true) + + input = new BN('15663360') + output = new BN('1208402137') + expect(feen(input).eq(output)).to.equal(true) + }) + + it('fend matches expected reference values', () => { + let input = new BN('1897766331') + let output = new BN('123456789') + expect(fend(input).eq(output)).to.equal(true) + + input = new BN('1208402137') + output = new BN('15663360') + expect(fend(input).eq(output)).to.equal(true) + }) +}) + +describe('fice/teil', () => { + it('fice and teil are inverses', () => { + let prop = jsc.forall(bignums, bn => + fice(teil(bn)).eq(bn) && teil(fice(bn)).eq(bn)) + + jsc.assert(prop) + }) + + it('fice matches expected reference values', () => { + let input = new BN ('123456789') + let output = new BN('2060458291') + expect(fice(input).eq(output)).to.equal(true) + + input = new BN('15663360') + output = new BN('1195593620') + expect(fice(input).eq(output)).to.equal(true) + }) + + it('teil matches expected reference values', () => { + let input = new BN('2060458291') + let output = new BN ('123456789') + expect(teil(input).eq(output)).to.equal(true) + + input = new BN('1195593620') + output = new BN('15663360') + expect(teil(input).eq(output)).to.equal(true) + }) +}) + diff --git a/test/property.test.js b/test/property.test.js @@ -1,29 +0,0 @@ -const { expect } = require('chai') -const jsc = require('jsverify') -const bn = require('bn.js') - -const ob = require('../src') - -describe('@q encoding properties', () => { - - let hexString = jsc.string.smap( - x => Buffer.from(x).toString('hex'), - x => Buffer.from(x, 'hex').toString() - ) - - let patq = hexString.smap(ob.hex2patq, ob.patq2hex) - - it('patq2hex and hex2patq are inverses', () => { - let iso0 = jsc.forall(hexString, hex => - ob._eqModLeadingZeroBytes(ob.patq2hex(ob.hex2patq(hex)), hex) - ) - - let iso1 = jsc.forall(patq, str => - ob.eqPatq(ob.hex2patq(ob.patq2hex(str)), str) - ) - - jsc.assert(iso0, { tests: 200 }) - jsc.assert(iso1, { tests: 200 }) - }) - -}) diff --git a/test/util.test.js b/test/util.test.js @@ -1,51 +0,0 @@ -const { expect } = require('chai'); -const { isEqual } = require('lodash') - -const ob = require('../src'); - -describe('utils', () => { - it('feen', () => { - expect(ob._feen(0x10100)).to.equal(0x63b30e1c); - }) - - it('fend', () => { - expect(ob._fend(0x63b30e1c)).to.equal(0x10100); - }) - - it('muk', () => { - expect(ob._muk(0, 2, 0x101)).to.equal(0x42081a9b); - expect(ob._muk(0, 2, 0x201)).to.equal(0x64c7667e); - }) - - it('getAt', () => { - expect(ob._getAt(['a', 'b', 'c'], 1)).to.equal('b'); - }); - - it('len', () => { - expect(ob._len(['a', 'b', 'c'])).to.equal(3); - }); - - it('lid', () => { - expect(ob._lid(['a', 'b', 'c'])).to.equal(2); - }); - - it('indexOf', () => { - expect(ob._indexOf(['a', 'b', 'c'], 'b')).to.equal(1); - }); - - it('isOdd', () => { - expect(ob._isOdd(3)).to.equal(true); - expect(ob._isOdd(0)).to.equal(false); - }) - - it('isEven', () => { - expect(ob._isEven(3)).to.equal(false); - expect(ob._isEven(0)).to.equal(true); - }); - - it('seq', () => { - expect(isEqual(ob._seq(3), [0, 1, 2])).to.equal(true); - }); - -}) -