[SERVER-57726] ZigZag encoder/decoder for signed 32bit and 64bit integer Created: 15/Jun/21  Updated: 29/Oct/23  Resolved: 02/Jul/21

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 5.1.0-rc0

Type: Task Priority: Major - P3
Reporter: Jackson Xie (Inactive) Assignee: Luke Bhan (Inactive)
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Duplicate
is duplicated by SERVER-57725 Simple-8b: Accept Signed Values Closed
Problem/Incident
Backwards Compatibility: Fully Compatible
Sprint: Execution Team 2021-06-28, Execution Team 2021-07-12
Participants:
Linked BF Score: 0

 Description   

Add a "ZigZag" encoder for signed integers that stores the sign bit as the least significant bit. Two's complement is using the most significant bit resulting in a large bit difference for -1 vs 0.

With ZigZag, Simple-8b encoder does then not have to know about signed integers and can treat everything as unsigned.

For 32bit integers ZigZag encoding would look like this:
zigzag = (n << 1) ^ (n >> 31)



 Comments   
Comment by Vivian Ge (Inactive) [ 06/Oct/21 ]

Updating the fixversion since branching activities occurred yesterday. This ticket will be in rc0 when it’s been triggered. For more active release information, please keep an eye on #server-release. Thank you!

Comment by Githook User [ 03/Jul/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-57726 Fix bson_util_test with ASAN builder: left shift of negative value -1
Branch: master
https://github.com/mongodb/mongo/commit/aa2ac023376c13d73ead07155abd0bbb67955a09

Comment by Githook User [ 02/Jul/21 ]

Author:

{'name': 'lukebhan', 'email': 'luke.bhan@vanderbilt.edu', 'username': 'lukebhan'}

Message: SERVER-57726 Added signed integer encoding to simple8b

changed decode to use or

updated zigzag

removed iostream

removed debug code

replace negate with 2's complement

fixed linter

linter
Branch: master
https://github.com/mongodb/mongo/commit/8544eebc9bf29710bb4158237e72bcd825466e23

Generated at Thu Feb 08 05:42:38 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.