Skip to content

Instantly share code, notes, and snippets.

@Vectorized
Last active June 16, 2023 08:51
Show Gist options
  • Save Vectorized/56ac210117f9baa15ac74a9ae779cd1f to your computer and use it in GitHub Desktop.
Save Vectorized/56ac210117f9baa15ac74a9ae779cd1f to your computer and use it in GitHub Desktop.
Solidity String Replace
// SPDX-License-Identifier: MIT
pragma solidity >=0.8.0;
library LibString {
function replace(
string memory subject,
string memory search,
string memory replacement
) internal pure returns (string memory result) {
assembly {
let subjectLength := mload(subject)
let searchLength := mload(search)
let replacementLength := mload(replacement)
// Store the mask for sub-word comparisons in the scratch space.
mstore(0x00, not(0))
mstore(0x20, 0)
subject := add(subject, 0x20)
search := add(search, 0x20)
replacement := add(replacement, 0x20)
result := add(mload(0x40), 0x20)
let k := 0
let subjectEnd := add(subject, subjectLength)
if iszero(gt(searchLength, subjectLength)) {
let subjectSearchEnd := add(sub(subjectEnd, searchLength), 1)
for {} lt(subject, subjectSearchEnd) {} {
let o := and(searchLength, 31)
// Whether the first `searchLength % 32` bytes of
// `subject` and `search` matches.
let l := iszero(and(xor(mload(subject), mload(search)), mload(sub(0x20, o))))
// Iterate through the rest of `search` and check if any word mismatch.
// If any mismatch is detected, `l` is set to 0.
for {} and(lt(o, searchLength), l) {} {
l := eq(mload(add(subject, o)), mload(add(search, o)))
o := add(o, 0x20)
}
// If `l` is one, there is a match, and we have to copy the `replacement`.
if l {
// Copy the `replacement` one word at a time.
for { o := 0 } lt(o, replacementLength) { o := add(o, 0x20) } {
mstore(add(result, add(k, o)), mload(add(replacement, o)))
}
k := add(k, replacementLength)
subject := add(subject, searchLength)
}
// If `l` or `searchLength` is zero.
if iszero(mul(l, searchLength)) {
mstore(add(result, k), mload(subject))
k := add(k, 1)
subject := add(subject, 1)
}
}
}
let resultRemainder := add(result, k)
k := add(k, sub(subjectEnd, subject))
// Copy the rest of the string one word at a time.
for {} lt(subject, subjectEnd) {} {
mstore(resultRemainder, mload(subject))
resultRemainder := add(resultRemainder, 0x20)
subject := add(subject, 0x20)
}
// Allocate memory for the length and the bytes, rounded up to a multiple of 32.
mstore(0x40, add(result, and(add(k, 64), not(31))))
result := sub(result, 0x20)
mstore(result, k)
}
}
}
// SPDX-License-Identifier: MIT
// Author: vectorized.eth
pragma solidity >=0.8.0;
import './LibString.sol';
contract LibStringMock {
function replace(
string memory subject,
string memory search,
string memory replacement
) external pure returns (string memory result) {
result = LibString.replace(subject, search, replacement);
}
}
const { expect } = require('chai');
const { BigNumber } = require('ethers');
const { constants } = require('@openzeppelin/test-helpers');
const { ZERO_ADDRESS } = constants;
const deployContract = async function (contractName, constructorArgs) {
let factory = await ethers.getContractFactory(contractName);
let contract = await factory.deploy(...(constructorArgs || []));
await contract.deployed();
return contract;
};
describe('LibString', function () {
beforeEach(async function () {
this.libStringMock = await deployContract('LibStringMock');
const [owner, addr1] = await ethers.getSigners();
this.owner = owner;
this.addr1 = addr1;
this.randomString = function (n) {
let s = '';
const characters = '0123456789';
for (let i = 0; i < n; ++i) {
s += characters.charAt(~~(Math.random() * 10));
}
return s;
}
});
it('Empty search', async function () {
let source = '123';
let search = '';
let replacement = 'aaa';
let replaced = source.replace(new RegExp('' + search, 'g'), replacement);
expect(await this.libStringMock.replace(source, search, replacement)).to.be.eq(replaced);
});
it('Fuzz test', async function () {
for (let i = 0; i < 1000; ++i) {
let n = ~~(Math.random() * 100);
let start = ~~(Math.random() * (n + 1));
let stop = ~~(Math.random() * (n + 1));
if (stop > start) {
let temp = start;
start = stop;
stop = temp;
}
let source = this.randomString(n);
let search = source.substring(start, stop);
let replacement = this.randomString(~~(Math.random() * 100));
let replaced = source.replace(new RegExp('' + search, 'g'), replacement);
expect(await this.libStringMock.replace(source, search, replacement)).to.be.eq(replaced);
}
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment