Skip to content

Instantly share code, notes, and snippets.

@mibli
Created March 8, 2024 00:29
Show Gist options
  • Save mibli/ea9ec153e2d2c8f20d7d1e9474c725e9 to your computer and use it in GitHub Desktop.
Save mibli/ea9ec153e2d2c8f20d7d1e9474c725e9 to your computer and use it in GitHub Desktop.
Optimized and readable byte sequence compare
// So the aim of this exercise is to make a bit easier on the eyes (and cpu)
// comparisons of array elements, than comparing byte, by byte.
// Imagine that we have protocol buffer represented by array of bytes:
//
// uint8_t buffer[] = { 42, 84, 54, 32, 06, 12, 14, 05 };
//
// Now we have some logic that has to check header of the buffer for key values
// Normally we would use structores, that we would assign values to... (let's skip that for now)
// Otherwise we would compare each byte, eg.
//
// bool isOurBoy = buffer[HEADER_START + 2] == 0x54 &&
// buffer[HEADER_START + 3] == 0x32 &&
// buffer[HEADER_START + 4] == 0x06;
//
// In this second case 1 it's annoying to read if Youre looking for exact
// sequence in source code. And 2. it's inefficient.
//
// The solution to that would be to compare to ready value eg. 0x543206...
//
// (reinterpret_cast<uint32_t>(buffer + HEAD_START + 2) & 0x00FFFFFF)
// == 0x00063254;
//
// Except now we our comparison value is reversed... But it will be faster
// and easier to use with combination with mask. But we can make compilator
// produce useful value from easy to read value we give it, with help of some
// constexpr magic.. So here we go.
#include <iostream>
char array[5] = { 0, 1, 2, 3, 4 };
template <typename uint_type>
constexpr uint_type make_msk(size_t num) {
uint_type res = 0;
while (num-- > 0)
res = (res << 8) | 0xFF;
return res;
}
template <typename uint_type>
constexpr uint_type make_cmp(uint_type num, size_t len) {
size_t word_size = sizeof(uint_type);
size_t empty_spaces = word_size - len;
uint_type res = 0;
for (int i = 0; i < word_size - empty_spaces; ++i)
// original shifted value -> bare -> aligned for endian
res |= ((num & (0xFF << 8 * i)) >> 8 * i) << 8 * (word_size - 1 - i - empty_spaces);
return res;
}
template <typename uint_type>
inline bool compare_by_int(char *arr, uint_type val, size_t num) {
return (*reinterpret_cast<uint_type *>(arr) & make_msk<uint_type>(num)) == make_cmp<uint_type>(val, num);
}
constexpr uint64_t mask = make_msk<uint64_t>(3);
constexpr uint64_t comparator = make_cmp<uint64_t>(0x01020304, 3);
int main() {
printf("%016x\n", mask);
printf("%016x\n", comparator);
printf("%08x\n", *reinterpret_cast<uint32_t *>(array + 1));
std::cout
<< ((*reinterpret_cast<uint32_t *>(array + 1) & 0x0000FFFF) == 0x00000201 ? "true" : "false")
<< std::endl
<< (compare_by_int(array + 2, 0x0203ul, 2) ? "true" : "false")
<< std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment