1  /*
  2   * @title Solidity Bytes Arrays Utils
  3   * @author Gonçalo Sá <goncalo.sa@consensys.net>
  4   *
  5   * @dev Bytes tightly packed arrays utility library for ethereum contracts written in Solidity.
  6   *      The library lets you concatenate, slice and type cast bytes arrays both in memory and storage.
  7   */
  8  pragma solidity >=0.5.0 <0.7.0;
  9  
 10  
 11  library BytesLib {
 12      function concat(
 13          bytes memory _preBytes,
 14          bytes memory _postBytes
 15      )
 16          internal
 17          pure
 18          returns (bytes memory)
 19      {
 20          bytes memory tempBytes;
 21  
 22          assembly {
 23              // Get a location of some free memory and store it in tempBytes as
 24              // Solidity does for memory variables.
 25              tempBytes := mload(0x40)
 26  
 27              // Store the length of the first bytes array at the beginning of
 28              // the memory for tempBytes.
 29              let length := mload(_preBytes)
 30              mstore(tempBytes, length)
 31  
 32              // Maintain a memory counter for the current write location in the
 33              // temp bytes array by adding the 32 bytes for the array length to
 34              // the starting location.
 35              let mc := add(tempBytes, 0x20)
 36              // Stop copying when the memory counter reaches the length of the
 37              // first bytes array.
 38              let end := add(mc, length)
 39  
 40              for {
 41                  // Initialize a copy counter to the start of the _preBytes data,
 42                  // 32 bytes into its memory.
 43                  let cc := add(_preBytes, 0x20)
 44              } lt(mc, end) {
 45                  // Increase both counters by 32 bytes each iteration.
 46                  mc := add(mc, 0x20)
 47                  cc := add(cc, 0x20)
 48              } {
 49                  // Write the _preBytes data into the tempBytes memory 32 bytes
 50                  // at a time.
 51                  mstore(mc, mload(cc))
 52              }
 53  
 54              // Add the length of _postBytes to the current length of tempBytes
 55              // and store it as the new length in the first 32 bytes of the
 56              // tempBytes memory.
 57              length := mload(_postBytes)
 58              mstore(tempBytes, add(length, mload(tempBytes)))
 59  
 60              // Move the memory counter back from a multiple of 0x20 to the
 61              // actual end of the _preBytes data.
 62              mc := end
 63              // Stop copying when the memory counter reaches the new combined
 64              // length of the arrays.
 65              end := add(mc, length)
 66  
 67              for {
 68                  let cc := add(_postBytes, 0x20)
 69              } lt(mc, end) {
 70                  mc := add(mc, 0x20)
 71                  cc := add(cc, 0x20)
 72              } {
 73                  mstore(mc, mload(cc))
 74              }
 75  
 76              // Update the free-memory pointer by padding our last write location
 77              // to 32 bytes: add 31 bytes to the end of tempBytes to move to the
 78              // next 32 byte block, then round down to the nearest multiple of
 79              // 32. If the sum of the length of the two arrays is zero then add
 80              // one before rounding down to leave a blank 32 bytes (the length block with 0).
 81              mstore(0x40, and(
 82                add(add(end, iszero(add(length, mload(_preBytes)))), 31),
 83                not(31) // Round down to the nearest 32 bytes.
 84              ))
 85          }
 86  
 87          return tempBytes;
 88      }
 89  
 90      function concatStorage(bytes storage _preBytes, bytes memory _postBytes) internal {
 91          assembly {
 92              // Read the first 32 bytes of _preBytes storage, which is the length
 93              // of the array. (We don't need to use the offset into the slot
 94              // because arrays use the entire slot.)
 95              let fslot := sload(_preBytes_slot)
 96              // Arrays of 31 bytes or less have an even value in their slot,
 97              // while longer arrays have an odd value. The actual length is
 98              // the slot divided by two for odd values, and the lowest order
 99              // byte divided by two for even values.
100              // If the slot is even, bitwise and the slot with 255 and divide by
101              // two to get the length. If the slot is odd, bitwise and the slot
102              // with -1 and divide by two.
103              let slength := div(and(fslot, sub(mul(0x100, iszero(and(fslot, 1))), 1)), 2)
104              let mlength := mload(_postBytes)
105              let newlength := add(slength, mlength)
106              // slength can contain both the length and contents of the array
107              // if length < 32 bytes so let's prepare for that
108              // v. http://solidity.readthedocs.io/en/latest/miscellaneous.html#layout-of-state-variables-in-storage
109              switch add(lt(slength, 32), lt(newlength, 32))
110              case 2 {
111                  // Since the new array still fits in the slot, we just need to
112                  // update the contents of the slot.
113                  // uint256(bytes_storage) = uint256(bytes_storage) + uint256(bytes_memory) + new_length
114                  sstore(
115                      _preBytes_slot,
116                      // all the modifications to the slot are inside this
117                      // next block
118                      add(
119                          // we can just add to the slot contents because the
120                          // bytes we want to change are the LSBs
121                          fslot,
122                          add(
123                              mul(
124                                  div(
125                                      // load the bytes from memory
126                                      mload(add(_postBytes, 0x20)),
127                                      // zero all bytes to the right
128                                      exp(0x100, sub(32, mlength))
129                                  ),
130                                  // and now shift left the number of bytes to
131                                  // leave space for the length in the slot
132                                  exp(0x100, sub(32, newlength))
133                              ),
134                              // increase length by the double of the memory
135                              // bytes length
136                              mul(mlength, 2)
137                          )
138                      )
139                  )
140              }
141              case 1 {
142                  // The stored value fits in the slot, but the combined value
143                  // will exceed it.
144                  // get the keccak hash to get the contents of the array
145                  mstore(0x0, _preBytes_slot)
146                  let sc := add(keccak256(0x0, 0x20), div(slength, 32))
147  
148                  // save new length
149                  sstore(_preBytes_slot, add(mul(newlength, 2), 1))
150  
151                  // The contents of the _postBytes array start 32 bytes into
152                  // the structure. Our first read should obtain the `submod`
153                  // bytes that can fit into the unused space in the last word
154                  // of the stored array. To get this, we read 32 bytes starting
155                  // from `submod`, so the data we read overlaps with the array
156                  // contents by `submod` bytes. Masking the lowest-order
157                  // `submod` bytes allows us to add that value directly to the
158                  // stored value.
159  
160                  let submod := sub(32, slength)
161                  let mc := add(_postBytes, submod)
162                  let end := add(_postBytes, mlength)
163                  let mask := sub(exp(0x100, submod), 1)
164  
165                  sstore(
166                      sc,
167                      add(
168                          and(
169                              fslot,
170                              0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00
171                          ),
172                          and(mload(mc), mask)
173                      )
174                  )
175  
176                  for {
177                      mc := add(mc, 0x20)
178                      sc := add(sc, 1)
179                  } lt(mc, end) {
180                      sc := add(sc, 1)
181                      mc := add(mc, 0x20)
182                  } {
183                      sstore(sc, mload(mc))
184                  }
185  
186                  mask := exp(0x100, sub(mc, end))
187  
188                  sstore(sc, mul(div(mload(mc), mask), mask))
189              }
190              default {
191                  // get the keccak hash to get the contents of the array
192                  mstore(0x0, _preBytes_slot)
193                  // Start copying to the last used word of the stored array.
194                  let sc := add(keccak256(0x0, 0x20), div(slength, 32))
195  
196                  // save new length
197                  sstore(_preBytes_slot, add(mul(newlength, 2), 1))
198  
199                  // Copy over the first `submod` bytes of the new data as in
200                  // case 1 above.
201                  let slengthmod := mod(slength, 32)
202                  let mlengthmod := mod(mlength, 32)
203                  let submod := sub(32, slengthmod)
204                  let mc := add(_postBytes, submod)
205                  let end := add(_postBytes, mlength)
206                  let mask := sub(exp(0x100, submod), 1)
207  
208                  sstore(sc, add(sload(sc), and(mload(mc), mask)))
209  
210                  for {
211                      sc := add(sc, 1)
212                      mc := add(mc, 0x20)
213                  } lt(mc, end) {
214                      sc := add(sc, 1)
215                      mc := add(mc, 0x20)
216                  } {
217                      sstore(sc, mload(mc))
218                  }
219  
220                  mask := exp(0x100, sub(mc, end))
221  
222                  sstore(sc, mul(div(mload(mc), mask), mask))
223              }
224          }
225      }
226  
227      function slice(
228          bytes memory _bytes,
229          uint _start,
230          uint _length
231      )
232          internal
233          pure
234          returns (bytes memory)
235      {
236          require(_bytes.length >= (_start + _length));
237  
238          bytes memory tempBytes;
239  
240          assembly {
241              switch iszero(_length)
242              case 0 {
243                  // Get a location of some free memory and store it in tempBytes as
244                  // Solidity does for memory variables.
245                  tempBytes := mload(0x40)
246  
247                  // The first word of the slice result is potentially a partial
248                  // word read from the original array. To read it, we calculate
249                  // the length of that partial word and start copying that many
250                  // bytes into the array. The first word we copy will start with
251                  // data we don't care about, but the last `lengthmod` bytes will
252                  // land at the beginning of the contents of the new array. When
253                  // we're done copying, we overwrite the full first word with
254                  // the actual length of the slice.
255                  let lengthmod := and(_length, 31)
256  
257                  // The multiplication in the next line is necessary
258                  // because when slicing multiples of 32 bytes (lengthmod == 0)
259                  // the following copy loop was copying the origin's length
260                  // and then ending prematurely not copying everything it should.
261                  let mc := add(add(tempBytes, lengthmod), mul(0x20, iszero(lengthmod)))
262                  let end := add(mc, _length)
263  
264                  for {
265                      // The multiplication in the next line has the same exact purpose
266                      // as the one above.
267                      let cc := add(add(add(_bytes, lengthmod), mul(0x20, iszero(lengthmod))), _start)
268                  } lt(mc, end) {
269                      mc := add(mc, 0x20)
270                      cc := add(cc, 0x20)
271                  } {
272                      mstore(mc, mload(cc))
273                  }
274  
275                  mstore(tempBytes, _length)
276  
277                  //update free-memory pointer
278                  //allocating the array padded to 32 bytes like the compiler does now
279                  mstore(0x40, and(add(mc, 31), not(31)))
280              }
281              //if we want a zero-length slice let's just return a zero-length array
282              default {
283                  tempBytes := mload(0x40)
284  
285                  mstore(0x40, add(tempBytes, 0x20))
286              }
287          }
288  
289          return tempBytes;
290      }
291  
292      function toAddress(bytes memory _bytes, uint _start) internal  pure returns (address) {
293          require(_bytes.length >= (_start + 20));
294          address tempAddress;
295  
296          assembly {
297              tempAddress := div(mload(add(add(_bytes, 0x20), _start)), 0x1000000000000000000000000)
298          }
299  
300          return tempAddress;
301      }
302  
303      function toUint8(bytes memory _bytes, uint _start) internal  pure returns (uint8) {
304          require(_bytes.length >= (_start + 1));
305          uint8 tempUint;
306  
307          assembly {
308              tempUint := mload(add(add(_bytes, 0x1), _start))
309          }
310  
311          return tempUint;
312      }
313  
314      function toUint16(bytes memory _bytes, uint _start) internal  pure returns (uint16) {
315          require(_bytes.length >= (_start + 2));
316          uint16 tempUint;
317  
318          assembly {
319              tempUint := mload(add(add(_bytes, 0x2), _start))
320          }
321  
322          return tempUint;
323      }
324  
325      function toUint32(bytes memory _bytes, uint _start) internal  pure returns (uint32) {
326          require(_bytes.length >= (_start + 4));
327          uint32 tempUint;
328  
329          assembly {
330              tempUint := mload(add(add(_bytes, 0x4), _start))
331          }
332  
333          return tempUint;
334      }
335  
336      function toUint64(bytes memory _bytes, uint _start) internal  pure returns (uint64) {
337          require(_bytes.length >= (_start + 8));
338          uint64 tempUint;
339  
340          assembly {
341              tempUint := mload(add(add(_bytes, 0x8), _start))
342          }
343  
344          return tempUint;
345      }
346  
347      function toUint96(bytes memory _bytes, uint _start) internal  pure returns (uint96) {
348          require(_bytes.length >= (_start + 12));
349          uint96 tempUint;
350  
351          assembly {
352              tempUint := mload(add(add(_bytes, 0xc), _start))
353          }
354  
355          return tempUint;
356      }
357  
358      function toUint128(bytes memory _bytes, uint _start) internal  pure returns (uint128) {
359          require(_bytes.length >= (_start + 16));
360          uint128 tempUint;
361  
362          assembly {
363              tempUint := mload(add(add(_bytes, 0x10), _start))
364          }
365  
366          return tempUint;
367      }
368  
369      function toUint(bytes memory _bytes, uint _start) internal  pure returns (uint256) {
370          require(_bytes.length >= (_start + 32));
371          uint256 tempUint;
372  
373          assembly {
374              tempUint := mload(add(add(_bytes, 0x20), _start))
375          }
376  
377          return tempUint;
378      }
379  
380      function toBytes32(bytes memory _bytes, uint _start) internal  pure returns (bytes32) {
381          require(_bytes.length >= (_start + 32));
382          bytes32 tempBytes32;
383  
384          assembly {
385              tempBytes32 := mload(add(add(_bytes, 0x20), _start))
386          }
387  
388          return tempBytes32;
389      }
390  
391      function equal(bytes memory _preBytes, bytes memory _postBytes) internal pure returns (bool) {
392          bool success = true;
393  
394          assembly {
395              let length := mload(_preBytes)
396  
397              // if lengths don't match the arrays are not equal
398              switch eq(length, mload(_postBytes))
399              case 1 {
400                  // cb is a circuit breaker in the for loop since there's
401                  //  no said feature for inline assembly loops
402                  // cb = 1 - don't breaker
403                  // cb = 0 - break
404                  let cb := 1
405  
406                  let mc := add(_preBytes, 0x20)
407                  let end := add(mc, length)
408  
409                  for {
410                      let cc := add(_postBytes, 0x20)
411                  // the next line is the loop condition:
412                  // while(uint(mc < end) + cb == 2)
413                  } eq(add(lt(mc, end), cb), 2) {
414                      mc := add(mc, 0x20)
415                      cc := add(cc, 0x20)
416                  } {
417                      // if any of these checks fails then arrays are not equal
418                      if iszero(eq(mload(mc), mload(cc))) {
419                          // unsuccess:
420                          success := 0
421                          cb := 0
422                      }
423                  }
424              }
425              default {
426                  // unsuccess:
427                  success := 0
428              }
429          }
430  
431          return success;
432      }
433  
434      function equalStorage(
435          bytes storage _preBytes,
436          bytes memory _postBytes
437      )
438          internal
439          view
440          returns (bool)
441      {
442          bool success = true;
443  
444          assembly {
445              // we know _preBytes_offset is 0
446              let fslot := sload(_preBytes_slot)
447              // Decode the length of the stored array like in concatStorage().
448              let slength := div(and(fslot, sub(mul(0x100, iszero(and(fslot, 1))), 1)), 2)
449              let mlength := mload(_postBytes)
450  
451              // if lengths don't match the arrays are not equal
452              switch eq(slength, mlength)
453              case 1 {
454                  // slength can contain both the length and contents of the array
455                  // if length < 32 bytes so let's prepare for that
456                  // v. http://solidity.readthedocs.io/en/latest/miscellaneous.html#layout-of-state-variables-in-storage
457                  if iszero(iszero(slength)) {
458                      switch lt(slength, 32)
459                      case 1 {
460                          // blank the last byte which is the length
461                          fslot := mul(div(fslot, 0x100), 0x100)
462  
463                          if iszero(eq(fslot, mload(add(_postBytes, 0x20)))) {
464                              // unsuccess:
465                              success := 0
466                          }
467                      }
468                      default {
469                          // cb is a circuit breaker in the for loop since there's
470                          //  no said feature for inline assembly loops
471                          // cb = 1 - don't breaker
472                          // cb = 0 - break
473                          let cb := 1
474  
475                          // get the keccak hash to get the contents of the array
476                          mstore(0x0, _preBytes_slot)
477                          let sc := keccak256(0x0, 0x20)
478  
479                          let mc := add(_postBytes, 0x20)
480                          let end := add(mc, mlength)
481  
482                          // the next line is the loop condition:
483                          // while(uint(mc < end) + cb == 2)
484                          for {} eq(add(lt(mc, end), cb), 2) {
485                              sc := add(sc, 1)
486                              mc := add(mc, 0x20)
487                          } {
488                              if iszero(eq(sload(sc), mload(mc))) {
489                                  // unsuccess:
490                                  success := 0
491                                  cb := 0
492                              }
493                          }
494                      }
495                  }
496              }
497              default {
498                  // unsuccess:
499                  success := 0
500              }
501          }
502  
503          return success;
504      }
505  }