From 05f1e9e3b8f5da593d949a1a18abba70568adb9c Mon Sep 17 00:00:00 2001 From: Greg Hysen Date: Thu, 31 May 2018 16:49:10 -0700 Subject: Resolved edge case in Memcpy where where send would eventually turn "negative" and wrap around. --- .../src/contracts/current/utils/LibMem/LibMem.sol | 28 ++- packages/contracts/test/libraries/lib_mem.ts | 270 +++++++++++---------- 2 files changed, 154 insertions(+), 144 deletions(-) (limited to 'packages') diff --git a/packages/contracts/src/contracts/current/utils/LibMem/LibMem.sol b/packages/contracts/src/contracts/current/utils/LibMem/LibMem.sol index f7ff4ca59..500044500 100644 --- a/packages/contracts/src/contracts/current/utils/LibMem/LibMem.sol +++ b/packages/contracts/src/contracts/current/utils/LibMem/LibMem.sol @@ -19,7 +19,7 @@ pragma solidity ^0.4.24; contract LibMem { - + function getMemAddress(bytes memory input) internal pure @@ -30,7 +30,7 @@ contract LibMem { } return address_; } - + /// @dev Copies `length` bytes from memory location `source` to `dest`. /// @param dest memory address to copy bytes to /// @param source memory address to copy bytes from @@ -58,7 +58,7 @@ contract LibMem { if (source == dest) { return; } - + // For large copies we copy whole words at a time. The final // word is aligned to the end of the range (instead of after the // previous) to handle partial words. So a copy will look like this: @@ -76,6 +76,9 @@ contract LibMem { // if (source > dest) { assembly { + // Record the total number of full words to copy + let nwords := div(length, 32) + // We subtract 32 from `send` and `dend` because it // is easier to compare with in the loop, and these // are also the addresses we need for copying the @@ -83,44 +86,47 @@ contract LibMem { length := sub(length, 32) let send := add(source, length) let dend := add(dest, length) - + // Remember the last 32 bytes of source // This needs to be done here and not after the loop // because we may have overwritten the last bytes in // source already due to overlap. let last := mload(send) - + // Copy whole words front to back - for {} lt(source, send) {} { + for {let i := 0} lt(i, nwords) {i := add(i, 1)} { mstore(dest, mload(source)) source := add(source, 32) dest := add(dest, 32) } - + // Write the last 32 bytes mstore(dend, last) } } else { assembly { + // Record the total number of full words to copy + let nwords := div(length, 32) + // We subtract 32 from `send` and `dend` because those // are the starting points when copying a word at the end. length := sub(length, 32) let send := add(source, length) let dend := add(dest, length) - + // Remember the first 32 bytes of source // This needs to be done here and not after the loop // because we may have overwritten the first bytes in // source already due to overlap. let first := mload(source) - + // Copy whole words back to front - for {} lt(source, send) {} { + for {let i := 0} lt(i, nwords) {i := add(i, 1)} { mstore(dend, mload(send)) send := sub(send, 32) dend := sub(dend, 32) } - + // Write the first 32 bytes mstore(dest, first) } diff --git a/packages/contracts/test/libraries/lib_mem.ts b/packages/contracts/test/libraries/lib_mem.ts index 225a8d60d..dd6f46742 100644 --- a/packages/contracts/test/libraries/lib_mem.ts +++ b/packages/contracts/test/libraries/lib_mem.ts @@ -11,13 +11,11 @@ const expect = chai.expect; // BUG: Ideally we would use Buffer.from(memory).toString('hex') // https://github.com/Microsoft/TypeScript/issues/23155 -const toHex = (buf: Uint8Array): string => - buf.reduce((a, v) => a + ('00' + v.toString(16)).slice(-2), '0x'); +const toHex = (buf: Uint8Array): string => buf.reduce((a, v) => a + ('00' + v.toString(16)).slice(-2), '0x'); -const fromHex = (str: string): Uint8Array => - Uint8Array.from(Buffer.from(str.slice(2), 'hex')); +const fromHex = (str: string): Uint8Array => Uint8Array.from(Buffer.from(str.slice(2), 'hex')); -describe('LibMem', () => { +describe.only('LibMem', () => { let owner: string; let testLibMem: TestLibMemContract; @@ -30,10 +28,9 @@ describe('LibMem', () => { }); describe('memcpy', () => { - // Create memory 0x000102...FF const memSize = 256; - const memory = (new Uint8Array(memSize)).map((_, i) => i); + const memory = new Uint8Array(memSize).map((_, i) => i); const memHex = toHex(memory); // Reference implementation to test against @@ -60,131 +57,138 @@ describe('LibMem', () => { test([[0, 0, 0, 'copies zero bytes with overlap']]); - describe('copies forward', () => test([ - [128, 0, 0, 'zero bytes'], - [128, 0, 1, 'one byte'], - [128, 0, 11, 'eleven bytes'], - [128, 0, 31, 'thirty-one bytes'], - [128, 0, 32, 'one word'], - [128, 0, 64, 'two words'], - [128, 0, 96, 'three words'], - [128, 0, 33, 'one word and one byte'], - [128, 0, 72, 'two words and eight bytes'], - [128, 0, 100, 'three words and four bytes'], - ])); - - describe('copies forward within one word', () => test([ - [16, 0, 0, 'zero bytes'], - [16, 0, 1, 'one byte'], - [16, 0, 11, 'eleven bytes'], - [16, 0, 16, 'sixteen bytes'], - ])); - - describe('copies forward with one byte overlap', () => test([ - [0, 0, 1, 'one byte'], - [10, 0, 11, 'eleven bytes'], - [30, 0, 31, 'thirty-one bytes'], - [31, 0, 32, 'one word'], - [32, 0, 33, 'one word and one byte'], - [71, 0, 72, 'two words and eight bytes'], - [99, 0, 100, 'three words and four bytes'], - ])); - - describe('copies forward with thirty-one bytes overlap', () => test([ - [0, 0, 31, 'thirty-one bytes'], - [1, 0, 32, 'one word'], - [2, 0, 33, 'one word and one byte'], - [41, 0, 72, 'two words and eight bytes'], - [69, 0, 100, 'three words and four bytes'], - ])); - - describe('copies forward with one word overlap', () => test([ - [0, 0, 32, 'one word'], - [1, 0, 33, 'one word and one byte'], - [41, 0, 72, 'two words and eight bytes'], - [69, 0, 100, 'three words and four bytes'], - ])); - - describe('copies forward with one word and one byte overlap', () => test([ - [0, 0, 33, 'one word and one byte'], - [40, 0, 72, 'two words and eight bytes'], - [68, 0, 100, 'three words and four bytes'], - ])); - - describe('copies forward with two words overlap', () => test([ - [0, 0, 64, 'two words'], - [8, 0, 72, 'two words and eight bytes'], - [36, 0, 100, 'three words and four bytes'], - ])); - - describe('copies forward within one word and one byte overlap', () => test([ - [0, 0, 1, 'one byte'], - [10, 0, 11, 'eleven bytes'], - [15, 0, 16, 'sixteen bytes'], - ])); - - describe('copies backward', () => test([ - [0, 128, 0, 'zero bytes'], - [0, 128, 1, 'one byte'], - [0, 128, 11, 'eleven bytes'], - [0, 128, 31, 'thirty-one bytes'], - [0, 128, 32, 'one word'], - [0, 128, 64, 'two words'], - [0, 128, 96, 'three words'], - [0, 128, 33, 'one word and one byte'], - [0, 128, 72, 'two words and eight bytes'], - [0, 128, 100, 'three words and four bytes'], - ])); - - describe('copies backward within one word', () => test([ - [0, 16, 0, 'zero bytes'], - [0, 16, 1, 'one byte'], - [0, 16, 11, 'eleven bytes'], - [0, 16, 16, 'sixteen bytes'], - ])); - - describe('copies backward with one byte overlap', () => test([ - [0, 0, 1, 'one byte'], - [0, 10, 11, 'eleven bytes'], - [0, 30, 31, 'thirty-one bytes'], - [0, 31, 32, 'one word'], - [0, 32, 33, 'one word and one byte'], - [0, 71, 72, 'two words and eight bytes'], - [0, 99, 100, 'three words and four bytes'], - ])); - - describe('copies backward with thirty-one bytes overlap', () => test([ - [0, 0, 31, 'thirty-one bytes'], - [0, 1, 32, 'one word'], - [0, 2, 33, 'one word and one byte'], - [0, 41, 72, 'two words and eight bytes'], - [0, 69, 100, 'three words and four bytes'], - ])); - - describe('copies backward with one word overlap', () => test([ - [0, 0, 32, 'one word'], - [0, 1, 33, 'one word and one byte'], - [0, 41, 72, 'two words and eight bytes'], - [0, 69, 100, 'three words and four bytes'], - ])); - - describe('copies backward with one word and one byte overlap', () => test([ - [0, 0, 33, 'one word and one byte'], - [0, 40, 72, 'two words and eight bytes'], - [0, 68, 100, 'three words and four bytes'], - ])); - - describe('copies backward with two words overlap', () => test([ - [0, 0, 64, 'two words'], - [0, 8, 72, 'two words and eight bytes'], - [0, 36, 100, 'three words and four bytes'], - ])); - - describe('copies forward within one word and one byte overlap', () => test([ - [0, 0, 1, 'one byte'], - [0, 10, 11, 'eleven bytes'], - [0, 15, 16, 'sixteen bytes'], - ])); - + describe('copies forward', () => + test([ + [128, 0, 0, 'zero bytes'], + [128, 0, 1, 'one byte'], + [128, 0, 11, 'eleven bytes'], + [128, 0, 31, 'thirty-one bytes'], + [128, 0, 32, 'one word'], + [128, 0, 64, 'two words'], + [128, 0, 96, 'three words'], + [128, 0, 33, 'one word and one byte'], + [128, 0, 72, 'two words and eight bytes'], + [128, 0, 100, 'three words and four bytes'], + ])); + + describe('copies forward within one word', () => + test([ + [16, 0, 0, 'zero bytes'], + [16, 0, 1, 'one byte'], + [16, 0, 11, 'eleven bytes'], + [16, 0, 16, 'sixteen bytes'], + ])); + + describe('copies forward with one byte overlap', () => + test([ + [0, 0, 1, 'one byte'], + [10, 0, 11, 'eleven bytes'], + [30, 0, 31, 'thirty-one bytes'], + [31, 0, 32, 'one word'], + [32, 0, 33, 'one word and one byte'], + [71, 0, 72, 'two words and eight bytes'], + [99, 0, 100, 'three words and four bytes'], + ])); + + describe('copies forward with thirty-one bytes overlap', () => + test([ + [0, 0, 31, 'thirty-one bytes'], + [1, 0, 32, 'one word'], + [2, 0, 33, 'one word and one byte'], + [41, 0, 72, 'two words and eight bytes'], + [69, 0, 100, 'three words and four bytes'], + ])); + + describe('copies forward with one word overlap', () => + test([ + [0, 0, 32, 'one word'], + [1, 0, 33, 'one word and one byte'], + [41, 0, 72, 'two words and eight bytes'], + [69, 0, 100, 'three words and four bytes'], + ])); + + describe('copies forward with one word and one byte overlap', () => + test([ + [0, 0, 33, 'one word and one byte'], + [40, 0, 72, 'two words and eight bytes'], + [68, 0, 100, 'three words and four bytes'], + ])); + + describe('copies forward with two words overlap', () => + test([ + [0, 0, 64, 'two words'], + [8, 0, 72, 'two words and eight bytes'], + [36, 0, 100, 'three words and four bytes'], + ])); + + describe('copies forward within one word and one byte overlap', () => + test([[0, 0, 1, 'one byte'], [10, 0, 11, 'eleven bytes'], [15, 0, 16, 'sixteen bytes']])); + + describe('copies backward', () => + test([ + [0, 128, 0, 'zero bytes'], + [0, 128, 1, 'one byte'], + [0, 128, 11, 'eleven bytes'], + [0, 128, 31, 'thirty-one bytes'], + [0, 128, 32, 'one word'], + [0, 128, 64, 'two words'], + [0, 128, 96, 'three words'], + [0, 128, 33, 'one word and one byte'], + [0, 128, 72, 'two words and eight bytes'], + [0, 128, 100, 'three words and four bytes'], + ])); + + describe('copies backward within one word', () => + test([ + [0, 16, 0, 'zero bytes'], + [0, 16, 1, 'one byte'], + [0, 16, 11, 'eleven bytes'], + [0, 16, 16, 'sixteen bytes'], + ])); + + describe('copies backward with one byte overlap', () => + test([ + [0, 0, 1, 'one byte'], + [0, 10, 11, 'eleven bytes'], + [0, 30, 31, 'thirty-one bytes'], + [0, 31, 32, 'one word'], + [0, 32, 33, 'one word and one byte'], + [0, 71, 72, 'two words and eight bytes'], + [0, 99, 100, 'three words and four bytes'], + ])); + + describe('copies backward with thirty-one bytes overlap', () => + test([ + [0, 0, 31, 'thirty-one bytes'], + [0, 1, 32, 'one word'], + [0, 2, 33, 'one word and one byte'], + [0, 41, 72, 'two words and eight bytes'], + [0, 69, 100, 'three words and four bytes'], + ])); + + describe('copies backward with one word overlap', () => + test([ + [0, 0, 32, 'one word'], + [0, 1, 33, 'one word and one byte'], + [0, 41, 72, 'two words and eight bytes'], + [0, 69, 100, 'three words and four bytes'], + ])); + + describe('copies backward with one word and one byte overlap', () => + test([ + [0, 0, 33, 'one word and one byte'], + [0, 40, 72, 'two words and eight bytes'], + [0, 68, 100, 'three words and four bytes'], + ])); + + describe('copies backward with two words overlap', () => + test([ + [0, 0, 64, 'two words'], + [0, 8, 72, 'two words and eight bytes'], + [0, 36, 100, 'three words and four bytes'], + ])); + + describe('copies forward within one word and one byte overlap', () => + test([[0, 0, 1, 'one byte'], [0, 10, 11, 'eleven bytes'], [0, 15, 16, 'sixteen bytes']])); }); }); -- cgit v1.2.3