[MONGOCRYPT-483] Support decimal128 Created: 12/Sep/22  Updated: 28/Oct/23  Resolved: 19/Jan/23

Status: Closed
Project: Libmongocrypt
Component/s: None
Affects Version/s: None
Fix Version/s: 1.7.0, 1.7.0-alpha2

Type: Task Priority: Major - P3
Reporter: Kevin Albertson Assignee: Colby Pike
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
depends on SERVER-68542 Add support for numerical encoding fo... Closed
Problem/Incident
causes MONGOCRYPT-594 Failed to build release from source code Closed
Related
Epic Link: libmongocrypt Support for Range Index
Binding Changes: Not Needed
Server Compat: 6.2

 Description   

Scope

  • Vendor a decimal128 library.
  • Support encoding, edge generation, and min cover of a BSON decimal128.

Background & Motivation

Relevant server code is in fle_crypto.cpp
Encoding in the server code is in getTypeInfoDecimal128 Port to mc-range-encoding.c.
Edge generation is in server code in getEdgesDecimal128. Port to mc-range-edge-generation.c.
MinCover is in server code in minCoverDecimal128. Port to mc-range-mincover.c.

This will require a dependency on a decimal128 library. DBX Scope: Driver Support for Range Index suggests "Import libtommath or tomsfastmath or similar to perform int128 math". The server vendors the Intel Decimal Floating-Point Math Library v2.1: https://github.com/mongodb/mongo/tree/master/src/third_party/IntelRDFPMathLib20U1



 Comments   
Comment by Githook User [ 25/Jan/23 ]

Author:

{'name': 'Kevin Albertson', 'email': 'kevin.albertson@mongodb.com', 'username': 'kevinAlbs'}

Message: MONGOCRYPT-483 make `CMAKE_BUILD_TYPE` configurable. (#532)

  • make CMAKE_BUILD_TYPE configurable

This enables the C driver to build with the same CMAKE_BUILD_TYPE as the C driver.

On Windows, a matching build type may be required. Mixing debug / release versions of the CRT may be problematic.

Comment by Githook User [ 25/Jan/23 ]

Author:

{'name': 'vector-of-bool', 'email': 'vectorofbool@gmail.com', 'username': 'vector-of-bool'}

Message: MONGOCRYPT-483: Support Decimal128 in range-based Queryable Encryption (#522)

  • Basic IntelDFP wrapper, and test tweaks:
  • Download and build IntelDFP as part of CMake configuration.
  • Modify the CHECK macro to be defined in a separate file to be reusable
    between tests.
  • Clean up DFP build, and patch for s390x
  • Suppress DFP warnings. It generates many, and we don't want them.
  • Define the OST encoding for Decimal128
  • Tweak bitstring generation and inline clz operations
  • Bit operations for u128
  • Edge generation for Decimal128
  • Modify mincover template to support non-builting types
  • mincover test vector data
  • New mincover impl for Decimal128
  • add decimal128 tests
  • Implement range-insert for decimal128
  • Implement find-range
  • Fix new conversion warning-errors
  • A safer strncpy ensures we write a null terminator
  • Handle case where 'min' is finer than 'precision'
  • We hit MSVC impl limits on string length:
  • Instead of using a newline-delimited string list, represent them as
    the array of strings directly. This also simplifies test code from
    needing to parse the strings.
  • Bump CMake min-required
  • Fix UB in IntellRDFP lib

Co-authored-by: Kevin Albertson <kevin.albertson@mongodb.com>
Branch: shreyaskalyan/MONGOCRYPT-509
https://github.com/mongodb/libmongocrypt/commit/b704947c2832745c680cc528bb37ce7e0747767b

Comment by Githook User [ 25/Jan/23 ]

Author:

{'name': 'Kevin Albertson', 'email': 'kevin.albertson@mongodb.com', 'username': 'kevinAlbs'}

Message: MONGOCRYPT-483 fix int128 test on big endian (#529)

  • print numerator and denominator on division failure
  • add rhel83 variant
  • copy endian.h
Comment by Githook User [ 20/Jan/23 ]

Author:

{'name': 'Kevin Albertson', 'email': 'kevin.albertson@mongodb.com', 'username': 'kevinAlbs'}

Message: MONGOCRYPT-483 make `CMAKE_BUILD_TYPE` configurable. (#532)

  • make CMAKE_BUILD_TYPE configurable

This enables the C driver to build with the same CMAKE_BUILD_TYPE as the C driver.

On Windows, a matching build type may be required. Mixing debug / release versions of the CRT may be problematic.

Comment by Githook User [ 18/Jan/23 ]

Author:

{'name': 'vector-of-bool', 'email': 'vectorofbool@gmail.com', 'username': 'vector-of-bool'}

Message: MONGOCRYPT-483: Support Decimal128 in range-based Queryable Encryption (#522)

  • Basic IntelDFP wrapper, and test tweaks:
  • Download and build IntelDFP as part of CMake configuration.
  • Modify the CHECK macro to be defined in a separate file to be reusable
    between tests.
  • Clean up DFP build, and patch for s390x
  • Suppress DFP warnings. It generates many, and we don't want them.
  • Define the OST encoding for Decimal128
  • Tweak bitstring generation and inline clz operations
  • Bit operations for u128
  • Edge generation for Decimal128
  • Modify mincover template to support non-builting types
  • mincover test vector data
  • New mincover impl for Decimal128
  • add decimal128 tests
  • Implement range-insert for decimal128
  • Implement find-range
  • Fix new conversion warning-errors
  • A safer strncpy ensures we write a null terminator
  • Handle case where 'min' is finer than 'precision'
  • We hit MSVC impl limits on string length:
  • Instead of using a newline-delimited string list, represent them as
    the array of strings directly. This also simplifies test code from
    needing to parse the strings.
  • Bump CMake min-required
  • Fix UB in IntellRDFP lib

Co-authored-by: Kevin Albertson <kevin.albertson@mongodb.com>
Branch: master
https://github.com/mongodb/libmongocrypt/commit/b704947c2832745c680cc528bb37ce7e0747767b

Comment by Githook User [ 18/Jan/23 ]

Author:

{'name': 'Kevin Albertson', 'email': 'kevin.albertson@mongodb.com', 'username': 'kevinAlbs'}

Message: MONGOCRYPT-483 fix int128 test on big endian (#529)

  • print numerator and denominator on division failure
  • add rhel83 variant
  • copy endian.h
Comment by Githook User [ 19/Dec/22 ]

Author:

{'name': 'vector-of-bool', 'email': 'vectorofbool@gmail.com', 'username': 'vector-of-bool'}

Message: MONGOCRYPT-483: A 128-bit integer abstraction (#510)

This changeset adds a new trivial type mlib_int128, which presents a method of performing 128-bit binary arithmetic. This is a prerequisite to MONGOCRYPT-483, which requires 128-bit integers and integer arithmetic.

Some platforms, such as 64-bit GCC, provide an __int128 abstraction, but other platforms do not. MSVC and all 32-bit targets do not have such extensions. For this reason, this PR implements 128-bit arithmetic using only standard C99.

The implementations of add, sub, the bitshifts, to/from string, compare, and equality are all fairly straightforward extensions of 64-bit operations (with carry/borrow).

Multiplication here is implemented using Knuth's 4.3.1M multiplication algorithm (from The Art of Computer Programming). Here 4.3.1M is used to multiply the two low 64-bit words to obtain the 128-bit product. The high word of the result is then adjusted by two more regular 64-bit multiplications.

Division is the most complicated operation and took a lot of testing to ensure correct. It uses Knuth's 4.3.1D algorithm for arbitrary precision unsigned division (defined in _mlibKnuth431D). Certain optimizations and shortcuts were learned from the constexpr implementations. Future optimizations to use intrinsics and hardware acceleration are not done here, since we just need these 128-bit integers for a few operations and want guaranteed platform-equivalence.

Most of the code has been marked as constexpr, and a lot of functionality is tested via static_asserts for failing CI as-fast-as-possible and immediate IDE feedback.
Branch: master
https://github.com/mongodb/libmongocrypt/commit/c8d5ffe9092962632c9cf33fac56bcf717911242

Generated at Thu Feb 08 09:08:47 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.