https://fgiesen.wordpress.com/2024/10/23/zero-or-sign-extend/ Skip to content Follow: RSS Twitter The ryg blog When I grow up I'll be an inventor. * Home * About * Coding * Compression * Computer Architecture * Demoscene * Graphics Pipeline * Maths * Multimedia * Networking * Papers * Stories * Thoughts * Uncategorized Zero or sign extend October 23, 2024 A while back I had to deal with a bit-packed format that contained a list of integer values encoded in one of a pre-defined sets of bit widths, where both the allowed bit widths and the signed-ness were denoted in a header elsewhere. These values never got particularly long (the largest bit width I needed to support was around 14 bits I think?) but having a mixture of different bit widths and signedness-es (is that a word?) was annoying to deal with, particularly the latter. Signed values were stored in the usual two's complement format. In particular, sign-extending narrow types is surprisingly awkward. Most people's go-to solution seems to be shifting the value up in a wider integer type to move the narrow value's sign bit into the containing types sign bit, then use an arithmetic shift to repeat the sign bit on the way down. That's a mouthful. I'm talking about code like this: int32 sign_extend(int32 val_11b) { int32 t = val_11b << (32 - 11); return t >> (32 - 11); } In C/C++, this explicitly relies on shifting something into the sign bit, which depending on the exact flavor of language standard you're using is either not allowed or at best fairly recently (voted into C++20) legal. It also explicitly needs to work with a fixed-size integer representation to know what to shift by. That's not a problem, just not aesthetically pleasing. There's a different way to sign-extend that works directly from the definition of two's complement and doesn't use any bit-shifting at all, though: all that two's complement really does is change the place value of the most significant bit. Take our example 11-bit integer, either signed or unsigned. No matter the type, bits 0 through 9 inclusive have place values of 1, 2, 4, .., 512. In an unsigned 11-bit integer, bit 10 has place value 1024; in a signed 11-bit integer, its place value is -1024 instead. So if we have an unsigned 11-bit value in some integer variable and want to convert it to the corresponding signed 11-bit value (assuming the original value was in two's complement form), we can do so without any shifting at all. Bits 0-9 retain their interpretation, but the value of bit 10 needs to have its sign flipped to turn unsigned into signed: int sign_extend(int val_11b) { return (val_11b & 0x3ff) - (val & 0x400); } We pass through bits 0 through 9, isolate bit 10 using val & 0x400 (which is either 0 if bit 10 wasn't set or 0x400=1024 if it was), and subtract the result. This form doesn't make any assumptions about the width of the used integer type or do anything undefined or implementation-specific, as long as the narrower values are small enough to never overflow the containing int type anyway. It doesn't even assume the compilation target uses two's complement! (Not that that's a big ask these days.) A minor variant is to skip the first mask entirely and think purely in terms of the correction we need to do. In our 11-bit example, if bit 10 was set, it contributes 1024 to the value when it should have contributed -1024, which is off by 2048 (twice the place value of that bit). This leads to a version with a single bit mask: int sign_extend(int val_11b) { return val - (val & 0x400) * 2; } Going back to my original problem, I had a mixture of different bit widths and needed to support either signed or unsigned. This can all be done by having two decoding variants, one for signed and one for unsigned, but with the formulation above, it's really easy to have the same code handle both: int zero_or_sign_extend(int val, int sign_bit) { return val - (val & sign_bit) * 2; } We read everything as unsigned initially. When they're meant to be that way, we pass 0 for sign_bit. For two's complement signed values, we pass 1 << (bit_width - 1). In my case this was determined at header decode time and stored along the bit widths. The code that actually interpreted the values used the above and didn't need to do any explicit tests for whether values were meant to be signed or unsigned anywhere. It's not earth-shattering, but it sure is neat! UPDATE: even nicer formulation suggested by Harold Aptroot: int zero_or_sign_extend(int val, int sign_bit) { return (val ^ sign_bit) - sign_bit; } This one is most easily understood by looking at it case by case. If sign_bit is 0 (unsigned case), both operations do nothing. Otherwise, it gives the mask for an actual sign bit. If that sign bit was originally clear (positive value), the initial XOR effectively adds the value of sign_bit, and then we immediately subtract it again, for a net contribution of 0. If the sign bit started out set, the XOR clears it (effectively subtracting sign_bit from val), and then we explicitly subtract it a second time, exactly like we needed to change the place value of that bit from +sign_bit to -sign_bit. Share this: * Facebook * X * Like Loading... Related From - Coding Leave a Comment Leave a comment Cancel reply [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] When is a BCn/ASTC endpoints-from-indices solve singular? >> * Recent Posts + Zero or sign extend + When is a BCn/ASTC endpoints-from-indices solve singular? + Oodle, Kraken etc. misconceptions + Entropy decoding in Oodle Data: x86-64 6-stream Huffman decoders + Computational complexity of texture encoding + A very brief BitKnit retrospective + Notes on FFTs: for implementers + Notes on FFTs: for users + What's that magic computation in stb__RefineBlock? + On AlphaTensor's new matrix multiplication algorithms * Categories + Coding + Compression + Computer Architecture + Demoscene + Graphics Pipeline + Maths + Multimedia + Networking + Papers + Stories + Thoughts + Uncategorized * Archives + October 2024 + August 2024 + October 2023 + July 2023 + May 2023 + March 2023 + November 2022 + October 2022 + September 2022 + April 2022 + October 2021 + August 2021 + July 2021 + July 2019 + April 2019 + February 2019 + December 2018 + September 2018 + March 2018 + February 2018 + January 2018 + December 2017 + November 2017 + September 2017 + August 2017 + April 2017 + October 2016 + August 2016 + April 2016 + March 2016 + February 2016 + January 2016 + December 2015 + October 2015 + September 2015 + July 2015 + May 2015 + February 2015 + December 2014 + October 2014 + August 2014 + July 2014 + June 2014 + May 2014 + March 2014 + February 2014 + December 2013 + November 2013 + October 2013 + September 2013 + August 2013 + July 2013 + June 2013 + May 2013 + March 2013 + February 2013 + January 2013 + August 2012 + July 2012 + June 2012 + April 2012 + March 2012 + February 2012 + November 2011 + October 2011 + September 2011 + August 2011 + July 2011 + May 2011 + February 2011 + January 2011 + December 2010 + November 2010 + October 2010 + September 2010 + August 2010 + March 2010 + December 2009 + October 2009 Blog at WordPress.com. * Comment * Subscribe Subscribed + [wpcom-] The ryg blog Join 480 other subscribers [ ] Sign me up + Already have a WordPress.com account? Log in now. * + [wpcom-] The ryg blog + Customize + Subscribe Subscribed + Sign up + Log in + Copy shortlink + Report this content + View post in Reader + Manage subscriptions + Collapse this bar %d [b]