Open Map Standard

infinite.md

uint256[]

uint256 layout;

Benefits: Supports infinitely large maps up to the gas limit Limitation: Doesn't use bytes as input, so the complexity to develop with could be more annoying without proper tooling

Solidity Helper Functions

/* Divide - Return quotient and remainder */
function getDivided(uint numerator, uint denominator) public pure returns(uint quotient, uint remainder) {
    require(denominator > 0);
    quotient  = numerator / denominator;
    remainder = numerator - denominator * quotient;
}

/* Bitwise Helper Functions */
function getBit(uint256[] memory map, uint256 pos) public pure returns(uint256) {
    (uint quotient, uint remainder) = getDivided(pos, 256);
    require(pos <= 255 + (quotient * 256));
    return (map[quotient] >> (255 - remainder)) & 1;
}

function setBit(uint256[] memory map, uint256 pos) public pure returns(uint256[] memory) {
    (uint quotient, uint remainder) = getDivided(pos, 256);
    require(pos <= 255 + (quotient * 256));
    map[quotient] = map[quotient] | 1 << (255 - remainder);

    return(map);
}

function addBits(uint256[] memory first, uint256[] memory second) public pure returns(uint256[] memory) {
    // Combines two maps by 'OR'ing the two together
    require(first.length == second.length);

    for (uint i = 0; i < first.length; i++) {
        first[i] = first[i] | second[i];
    }

    return first;
}

function subtractBits(uint256[] memory first, uint256[] memory second) public pure returns(uint256[] memory) {
    // Removes the second map from the first by 'AND'ing the two together
    require(first.length == second.length);

    for (uint i = 0; i < first.length; i++) {
        first[i] = first[i] & ~(second[i]);
    }

    return first;
}

function getBytes(uint256[] memory data) public view returns(bytes memory) {
    bytes memory output;

    for (uint i = 0; i < data.length; i++) {
        output = abi.encodePacked(output, data[i]);
    }

    return output;
}

bytes array (containing any # of uint256's)

bytes layout;

Benefits: Supports infinitely large maps up to the gas limit Limitation: The code complexity is higher than a more tightly defined structure

Only difference here from the above is the addition of a few helper functions. This allows for the usage of bytes as the input instead of uint256[]. It's assumed all functions are internal, so will be called at a top level function which does everything. It is directly built on top of the above structure

Solidity Data structure

uint256[] layout;

Solidity Helper Functions

/* Conversion functions between bytes <--> uint256[] */

/* Calculate the number of ints needed to contain the number of bytes in data */
function getNumIntsRequired(bytes memory data) public view returns(uint) {
    require(data.length > 0);

    (uint quotient, uint remainder) = getDivided(data.length, 32);

    if (remainder > 0) return quotient + 1;
    return quotient;
}

/* Gets a uint256 array from bytes */
function getIntArr(bytes memory data) public view returns(uint256[] memory) {
    uint num = getNumIntsRequired(data);
    uint256[] memory result = new uint256[](num);

    uint offset = 0;
    uint256 x;

    for (uint i = 0; i < num; i++) {
        assembly {
            x := mload(add(data, add(0x20, offset)))
            mstore(add(result, add(0x20, offset)), x)
        }
        offset += 0x20;
    }

    return result;
}

function getBytes(uint256[] memory data) public view returns(bytes memory) {
    bytes memory output;

    for (uint i = 0; i < data.length; i++) {
        output = abi.encodePacked(output, data[i]);
    }

    return output;
}