sodis.js

const { BN } = require('bn.js');
const { keccak256 } = require('ethereumjs-util');
const { toBN } = require('web3-utils');

// function hash (selector, salt, m) {
//     return new BN(selector, 'hex').xor(toBN(salt)).toNumber() % 25469 % m;
// }

function hash (selector, salt, m) {
    const saltStr = toBN(salt).toString('hex', 8);
    const hash = keccak256(Buffer.from(selector + saltStr, 'hex'));
    return toBN(hash.toString('hex')).modn(m);
}

function checkForExactMatch (selectors, salt) {
    for (let i = 0; i < selectors.length; i++) {
        if (hash(selectors[i], salt, selectors.length) != i) {
            return false;
        }
    }
    return true;
}

function checkForNonCollision (selectors, salt, m) {
    const set = new Set();
    for (let i = 0; i < selectors.length; i++) {
        const h = hash(selectors[i], salt, m);
        if (set.has(h)) {
            return false;
        }
        set.add(h);
    }
    return true;
}

const checkForBuckets = (max) => (selectors, salt, m) => {
    const map = new Map();
    for (let i = 0; i < selectors.length; i++) {
        const h = hash(selectors[i], salt, m);
        if (map[h] > max) {
            return false;
        }
        map[h] = map[h] + 1 || 1;
    }
    return true;
}

function findSalt (selectors, m, iterations, func) {
    for (let salt = 1; salt < iterations; salt++) {
        if (salt % 10000000 == 0) {
            console.log('salt', salt);
        }
        if (func(selectors, salt, m)) {
            return salt;
        }
    }
}

const signatures = [
    'calculateLeftovers(address,uint256)',
    'processLeftovers(address,address,uint256,uint256,uint256)',
    'patchCallWithTokenBalance(bytes,uint256,address,uint256)',
    'patchCallsWithTokenBalance(bytes[],uint256[],address,uint256)',
    'patchCallWithArbitraryCall(bytes,uint256,address,bytes)',
    'patchCallsWithArbitraryCall(bytes[],uint256[],address,bytes)',
    'querySellQuoteToken(address,uint256)',
    'swapUniV2(address,address,address,uint256,uint256)',
    'swapBrokenUniV2(address,address,address,uint256,uint256)',
    'swapUniV2Scaled(address,address,address,uint256,uint256)',
    'swapBrokenUniV2Scaled(address,address,address,uint256,uint256)',
];

console.log('Signatures =', signatures);

const selectors = signatures.map(Buffer.from).map(keccak256).map(s => s.toString('hex').substring(0, 8));

if ((new Set(selectors)).size !== selectors.length) {
    throw new Error('Duplicates found in selectors');
}

console.log('Selectors =', selectors);

const salt = findSalt(
    selectors,
    Math.round(selectors.length * 1),
    4000000000,
    checkForNonCollision
);
console.log('Found salt =', salt);

if (salt) {
    console.log('Indexes =', selectors.map(s => hash(s, salt, selectors.length)));
    const sortedIndexes = selectors.map((s,i) => [hash(s, salt, selectors.length), i]).sort(([a], [b]) => a - b);
    console.log('Sorted indexes =', sortedIndexes);
    console.log('Lookup =', sortedIndexes.map(([i,s]) => '(' + s + ' << ' + (248-i*8) + ')').join(' | '));
}