Skip to content

Instantly share code, notes, and snippets.

@ItsCuzzo

ItsCuzzo/CityAsm.sol

Created September 22, 2022 08:33
Show Gist options
  • Save ItsCuzzo/4d671e307339a617a9e4001aff58fff0 to your computer and use it in GitHub Desktop.
Save ItsCuzzo/4d671e307339a617a9e4001aff58fff0 to your computer and use it in GitHub Desktop.
Download ZIP
The core functionality from my "Optimising Gamified 2D Grid Movement" series on Medium.
Raw
CityAsm.sol
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.17;
import { ICity } from "./interfaces/ICity.sol";
/// @title Inspired by the Hobo Wars daily event of city exploration.
/// @author ItsCuzzo
/// @dev Source: https://wiki.hobowars.com/index.php?title=Exploring
/// Memory layout per invoke, assumes the transaction succeeds. Numbers provided
/// here are indicative of the 'happy' path.
///
/// -----------------------------------------------------------------------------
/// | Offset | Writes | Description |
/// |-----------------------------------------------------------------------------|
/// | 0x00 | 3 | Scratch space for hashing methods. |
/// | 0x20 | 3 | Scratch space for hashing methods. |
/// | 0x40 | 0 | Free memory pointer. |
/// | 0x60 | 0 | Zero slot. |
/// | 0x80 | 1 | Stores `block.timestamp` value. |
/// | 0xA0 | 100 | Stores `position` value. |
/// | 0xC0 | 25 | Stores `i` value. |
/// | 0xE0 | 100 | Stores magic value as defined in Solidity implementation. |
/// -----------------------------------------------------------------------------
contract CityAsm is ICity {
/// @dev The state variables defined in the Solidity implementation have been
/// packed into a single storage slot. This optimisation drastically reduces
/// the number of SLOADs that are required within our `explore` logic.
///
/// `0x73209C3093A80` is a hex value with the variables below packed as follows.
///
/// -------------------------------------------------------------------------------------------------
/// | Bit Position | Type & Value | Description |
/// |-------------------------------------------------------------------------------------------------|
/// | 0...23 | uint24(7 days) | cooldown: Duration a player must wait between explorations. |
/// | 24..39 | uint16(2499) | mapSize: Number of tiles within the grid, inclusive of 0. |
/// | 40..47 | uint8(50) | lootChance: Chance a player has to find loot at a given tile. |
/// | 48..55 | uint8(7) | maxCans: Maximum number of cans that be found at a tile. |
/// -------------------------------------------------------------------------------------------------
///
uint256 public config = 0x73209C3093A80;
/// @dev Maps an `address` to a packed `uint256`. The `uint256` value is packed as follows:
///
/// ---------------------------------------------------------------------------------------
/// | Bit Position | Type | Description |
/// |---------------------------------------------------------------------------------------|
/// | 0....127 | uint128 | lastExplore: Timestamp of the last invoke of `explore`. |
/// | 128..191 | uint64 | cansFound: Total number of cans found by the player. |
/// | 192..255 | uint64 | nonce: Used to roll starting position of the player. |
/// ---------------------------------------------------------------------------------------
///
mapping(address => uint256) private _players;
/// @notice Function used to explore the city.
/// @param moves Hex representation of the desired move set.
function explore(bytes32 moves) external {
assembly {
/// Assign `c` the `config` value from storage.
let c := sload(config.slot)
/// Parse out the value of `mapSize` from `c`. We do this by shifting the
/// value of `c` by 24 bits to the right and then masking out the 16 least
/// significant bits using `0xFFFF`.
let size := and(shr(24, c), 0xFFFF)
/// Parse out the value of `lootChance` from `c`. We do this by shifting the
/// value of `c` by 40 bits to the right and then masking out the 8 least
/// significant bits using `0xFF`.
let chance := and(shr(40, c), 0xFF)
/// Parse out the value of `maxCans` from `c`. We do this by shifting the
/// value of `c` by 48 bits to the right and then masking out the 8 least
/// significant bits using `0xFF`.
let max := and(shr(48, c), 0xFF)
/// Calculate the storage slot of `_players[msg.sender]`.
/// Source: https://docs.soliditylang.org/en/v0.8.17/internals/layout_in_storage.html
mstore(0x00, caller())
mstore(0x20, _players.slot)
/// Cache the storage slot of `players[msg.sender]` as we will need to reuse it
/// later. Caching this value will allow us to easily write to this storage slot
/// at a later point in time as we don't need to recalculate the value.
let p := keccak256(0x00, 64)
/// Cache the value of storage slot `players[msg.sender]` as it will be
/// used twice. Doing this avoids the need for an additional SLOAD.
let v := sload(p)
/// Check if `msg.sender` is on cooldown. To do so, we mask out both the `lastExplore`
/// value from `v` and the `cooldown` value from `c`. If they are, store the error
/// selector of `Exhausted()` in memory and revert.
if iszero(gt(sub(timestamp(), and(v, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)), and(c, 0xFFFFFF))) {
mstore(0x00, 0x6f3d6c4f)
revert(0x1c, 0x04)
}
/// Assign `cans` the value of `cansFound` from `_players[msg.sender]`.
let cans := and(shr(128, v), 0xFFFFFFFFFFFFFFFF)
/// Parse out the `nonce` value from `players[msg.sender]`. We do this by
/// shifting the value of `v` 192 bits to the right and then masking
/// out the 64 least significant bits using `0xFFFFFFFFFFFFFFFF`.
let nonce := and(shr(192, v), 0xFFFFFFFFFFFFFFFF)
/// Store both `caller` and `nonce` in scratch space.
mstore(0x00, caller())
mstore(0x20, nonce)
/// Calculate the starting position of the player. We add 1 to
/// ensure that `pos` can fall within the limits of 0 to `mapSize`.
let pos := add(mod(keccak256(0x00, 64), size), 1)
/// Define a variable `i` that will be used to track each iteration
/// of our for loop.
let i
/// Define a variable `set` that will be assigned a series of 4
/// moves (1 byte) from `moves`.
let set
/// Define a variable `change` that will be used to track the
/// value that `pos` will change by.
let change
/// Define a variable `move` that will be assigned a singular
/// move value in the limits of 0 to 3.
let move
/// Define a variable `eventId` that will be assigned a value
/// to be used in loot rolling.
let eventId
/// Since `block.timestamp` is used multiple times throughout our
/// loot rolling process, we can store it once in memory and reuse
/// it. This works because `block.timestamp` is guaranteed to remain
/// constant throughout execution and will not change.
mstore(0x80, timestamp())
/// Instead of using a 'traditional' assembly for loop, we opt to use
/// a more optimised implementation as showcased by @optimizoor.
///
/// Source: https://www.twitter.com/SolidityFridays/status/1568168481324933121
///
for {} 1 {} {
/// Assign `set` the value of `moves[i]`. `set` now holds a uint8 value
/// that represents the 4 moves associated with byte `i`.
set := byte(i, moves)
/// You might notice that we no longer have an inner loop. One gas optimisation
/// trick that was utilised here is loop unrolling. It's relatively niche to
/// encounter situations where this can be used and one of the unfortunate side
/// effects is that it comes with repetitiveness and hindered readability.
/// Parse Move 1.
/// Since moves are read from left-to-right, we shift `set` by 6 bits. Since
/// we are only working with a single byte value at a time, we can safely assume
/// that the upper bits of `set` are clean.
///
/// E.g. 11 00 01 00 >> 6 = 00 00 00 11
///
move := shr(6, set)
/// Another nifty gas optimisation that saves around 350 gas. This is a branchless
/// implementation of an if/else if/else statement inspired from @fiveoutofnine.
///
/// Source: https://www.twitter.com/fiveoutofnine/status/1491894008049811458
///
change := and(shr(shl(3, move), 0x32010132), 0xFF)
/// This switch statement is a beautiful example of when things just work. After
/// implementing the above logic, I needed a way to determine if the value of `pos` was
/// getting incremented or decremented.
///
/// If you recall the way movement within our system works, movements in either the
/// left (2) or up (3) directions result in a tile decrease and movements
/// in either the right (1) or down (0) directions result in a tile increase.
///
/// Since values of 1 and 0 result in a tile increase, we can simply shift the value
/// of `move` to the right by 1 and then check the value. If the value is 0, that means
/// we need to increment `pos`. If it's not, we decrement it.
///
switch shr(1, move)
case 0 { pos := add(pos, change) }
default { pos := sub(pos, change) }
/// Check if the player has moved out of bounds. If they have, we store the error
/// selector for `OutOfBounds()` in scratch space and revert.
if gt(pos, size) {
mstore(0x00, 0xb4120f14)
revert(0x1c, 0x04)
}
/// The next portion of code is responsible for rolling to determine if a player has
/// found any cans at their current position. The Solidity implementation equivalent is:
///
/// keccak256(abi.encode(block.timestamp, position, i, j));
///
/// Since we aren't using an inner loop, we have to provide a magic value to match the
/// conditions of the Solidity implementation.
///
mstore(0xA0, pos)
mstore(0xC0, i)
mstore(0xE0, 0)
/// Calculate the `eventId` seed.
eventId := keccak256(0x80, 128)
/// Calculate if the player has found any cans, if so, how many cans did they find?
if lt(mod(eventId, 100), chance) {
cans := add(cans, add(mod(eventId, max), 1))
}
/// Parse Move 2.
move := and(shr(4, set), 0x3)
change := and(shr(shl(3, move), 0x32010132), 0xFF)
switch shr(1, move)
case 0 { pos := add(pos, change) }
default { pos := sub(pos, change) }
if gt(pos, size) {
mstore(0x00, 0xb4120f14)
revert(0x1c, 0x04)
}
mstore(0xA0, pos)
mstore(0xE0, 2)
eventId := keccak256(0x80, 128)
if lt(mod(eventId, 100), chance) {
cans := add(cans, add(mod(eventId, max), 1))
}
/// Parse Move 3.
move := and(shr(2, set), 0x3)
change := and(shr(shl(3, move), 0x32010132), 0xFF)
switch shr(1, move)
case 0 { pos := add(pos, change) }
default { pos := sub(pos, change) }
if gt(pos, size) {
mstore(0x00, 0xb4120f14)
revert(0x1c, 0x04)
}
mstore(0xA0, pos)
mstore(0xE0, 4)
eventId := keccak256(0x80, 128)
if lt(mod(eventId, 100), chance) {
cans := add(cans, add(mod(eventId, max), 1))
}
/// Parse Move 4.
move := and(set, 0x3)
change := and(shr(shl(3, move), 0x32010132), 0xFF)
switch shr(1, move)
case 0 { pos := add(pos, change) }
default { pos := sub(pos, change) }
if gt(pos, size) {
mstore(0x00, 0xb4120f14)
revert(0x1c, 0x04)
}
mstore(0xA0, pos)
mstore(0xE0, 6)
eventId := keccak256(0x80, 128)
if lt(mod(eventId, 100), chance) {
cans := add(cans, add(mod(eventId, max), 1))
}
/// Once code within the for loop has finished executing, we update our
/// iterator value, check to see if the stated condition has been met, and
/// continue onwards.
i := add(i, 1)
if iszero(lt(i, 25)) { break }
}
/// Update the `_players` mapping with the respective values packed
/// into a single word.
sstore(
p,
or(or(timestamp(), shl(128, cans)), shl(192, add(nonce, 1)))
)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment