5 ms·
Inserting a 0 bit in the middle of a value
- tromp 2y agouint64 insert_zero_bit(uint64 value, int pos) { uint64 top_mask = ~0u64 << pos; return value + (value & top_mask); } > It only works for inserting exactly 1 bit But is easily generalized to inserting k bits: return value + ((1<<k)-1) * (value & top_mask);
- badmintonbaseba 2y agoNice bit twiddling hack! There are also the PDEP and PEXT instructions on x86 that could be used for this purpose, but it's possibly not worth it here.
- tubs 2y agoOn arm you can use https://developer.arm.com/documentation/dui0489/i/arm-and-thumb-instructions/bfc https://developer.arm.com/documentation/dui0489/i/arm-and-th... which is pretty convenient for this use-case.
- dan-robertson 2y agoAm I missing something or does that instruction only clear bits in the field and not shift the adjacent bits to contract the field to be empty?
- Retr0id 2y agoI wonder if the compiler is smart enough to emit those instructions with the right optimization flags
- badmintonbaseba 2y agoI never saw a compiler generating these instructions on its own. Compilers do produce popcnt and bswap from recognized algorithms, so I guess it's not entirely unreasonable, but I think the benefit would be marginal.
- fmbb 2y ago> there’s only ever between 1 and 3 anchor bits How often are these texturers transfered and how small are they? Doing all this to avoid sending at most three bits for a texture file sounds like a colossal waste of human life and of money.
- deleted 2y ago[deleted]
- elpocko 2y agoNot per file, per block of 16 pixels. They are transferred quite often - BCn is a texture compression scheme for realtime use in GPUs. Those textures are stored and processed in compressed form. https://en.wikipedia.org/wiki/S3_Texture_Compression https://en.wikipedia.org/wiki/S3_Texture_Compression
- explodingwaffle 2y agoThe more and more bit-hacks I see, the more convinced I am that they should be handled by a cleverer compiler. Some intrinsic(s) where you say “do x, y, to these bits” and it just figures out the optimum way of doing it for whatever platform you compile for.
- jsheard 2y agoThis tool is handy if you want a specific bit shuffle: https://programming.sirrida.de/calcperm.php https://programming.sirrida.de/calcperm.php It doesn't always find the optimal solution but it usually gets close.
- explodingwaffle 2y agothat page + the book Hacker's Delight are a big part of the reason I am so convinced of this :) If compilers/languages/standard libraries provided these bit permutations, and it was just something ~everyone had learned, it would be a lot easier to work with bits without needing to come up with the bitwise ops (or use that generator). In addition it would probably make better use of the hardware: sure, people like to pretend that we’re still programming C for PDP11, but modern hardware supports more operations than C has operators for (RISC-V B extension and co have the right idea <3) Modern compilers are probably pretty good? but I doubt they are perfect at turning code like that in OP into the best instructions. It is probably a bit late for C/C++ though. maaaybe possible to get it into LLVM and Rust.
- PhilipRoman 2y agoThat's a really cool side. Sad that it doesn't allow duplicate indices. I tried implementing the same thing but with support for duplicates and it was definitely a humbling exercise. I'm curious if there is any formal mathematical theory for this (shifted-off bits would probably make it less elegant than pure rotation)
- sixthDot 2y agoWell it is already the case, for example things like ROR or ROL are generated by optimizers[1] from certain patterns of bitops. [1]: https://godbolt.org/z/eE1cx9GT4 https://godbolt.org/z/eE1cx9GT4
- AXbsk14228 2y ago[flagged]
- pavlov 2y agoFor smaller integers, SIMD bit permute instructions can be used to do this kind of thing rapidly and with arbitrary reordering of the bits.
- deleted 2y ago[deleted]