Long unsigned integer math library

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

I'm wondering if there is any interest in the library whose man
page is attached, as I would like to donate it.  It provides very
limited (but still quite useful) support for operations involving
128 bit unsigned integers, and the functions implement operations
which are exactly those you would like to have efficiently done if
you are trying to write a more general library to deal with long
integers.  I haven't found similar library support anywhere,
though I may be missing something.

The reason I'd like to donate it is a little bit selfish.  While
I have decent, portable C language code for all the functions the
end result can be much improved if you can #include inline
definitions for those operations which are supported directly
by the hardware in the machine you are running on, and most CPU
architectures provide support for at least a few of them (x86_64
can inline all of them, most to single instructions).  I've
found, however, that this is a lot harder to manage in a
private library than it would be if the appropriate inlines
could always be found as <machine/ulmath_machdep.h>, with
the added bonus that having an empty .h file in the include
directory of some port I can't test code for might prompt
someone who can to fill in the bits that CPU can do.

While my primary use of these is user level software, I also
have my eye on some bits in the kernel which can be significantly
improved by being able to carry 128 bits through the intermediate
results of computations.

Dennis Ferguson

LIBULMATH(3)               Library Functions Manual               LIBULMATH(3)

NNAAMMEE
     uuccllzz3322, uuccllzz6644, uummuull6644, 
uummuull112288, uummuull112288hhii, uuddiivv6644, 
uuddiivv112288 -- perform
     unsigned long integer math operations

LLIIBBRRAARRYY
     Unsigned Long Integer Math Library (libulmath, -lulmath)

SSYYNNOOPPSSIISS
     ##iinncclluuddee <<uullmmaatthh..hh>>

     _i_n_t
     uuccllzz3322(_u_i_n_t_3_2___t _x);

     _i_n_t
     uuccllzz6644(_u_i_n_t_6_4___t _x);

     _u_i_n_t_6_4___t
     uummuull6644(_u_i_n_t_3_2___t _x, _u_i_n_t_3_2___t 
_y);

     _u_1_2_8_i_n_t___t
     uummuull112288(_u_i_n_t_6_4___t _x, 
_u_i_n_t_6_4___t _y);

     _u_i_n_t_6_4___t
     uummuull112288hhii(_u_i_n_t_6_4___t _x, 
_u_i_n_t_6_4___t _y);

     _u_6_4_d_i_v___t
     uuddiivv6644(_u_i_n_t_6_4___t _n_u_m, 
_u_i_n_t_3_2___t _d_e_n_o_m);

     _u_1_2_8_d_i_v___t
     uuddiivv112288(_u_1_2_8_i_n_t___t _n_u_m, 
_u_i_n_t_6_4___t _d_e_n_o_m);

DDEESSCCRRIIPPTTIIOONN
     The functions available in the _l_i_b_u_l_m_a_t_h library are 
intended to provide
     efficient support for multiplying and dividing unsigned integers with bit
     lengths longer than those supported by the compiler and/or the underlying
     machine hardware either directly, as in the case of the functions which
     operate on 128 bit integers, or as components for building more complex
     functions. To the extent possible the routines have been designed to map
     directly to instructions, or short instruction sequences, which sometimes
     exist on particular CPU architectures but which are seldom useful to, or
     generated by, compilers.

     The structures _u_1_2_8_i_n_t___t, _u_6_4_d_i_v___t and 
_u_1_2_8_d_i_v___t are defined in
     <_u_l_m_a_t_h_._h> to hold various argument and return types. The 
_u_1_2_8_i_n_t___t
     structure is used to pass 128 bit integer values and has as members:

        uint64_t        lo;     /* low order 64 bits */
        uint64_t        hi;     /* high order 64 bits */

     The _u_6_4_d_i_v___t structure is used to return the unsigned 32 
bit quotient and
     remainder resulting from the division of a 64 bit integer by a 32 bit
     integer, and includes the members:

        uint32_t        quot;   /* 32 bit quotient from division */
        uint32_t        rem;    /* 32 bit remainder from division */

     The _u_1_2_8_d_i_v___t structure is used analogously to return 
the results from
     128/64 bit divides, and has the following members:

        uint64_t        quot;   /* 64 bit quotient from division */
        uint64_t        rem;    /* 64 bit remainder from division */

     The uuccllzz3322() function counts the number of contiguous 0 bits 
starting at
     the high order end of the non-zero unsigned 32 bit integer argument _x,
     returning a value in the range 0-31 inclusive. The result of calling
     uuccllzz3322() with a zero-valued argument is undefined.

     uuccllzz6644() counts the number of contiguous 0 bits starting at 
the high
     order end of the non-zero unsigned 64 bit integer argument _x, returning a
     value in the range 0-63 inclusive. The result of calling 
uuccllzz6644() with a
     zero-valued argument is undefined.

     uummuull6644() multiplies its two 32 bit arguments, computing 
_x_*_y, and returns
     the 64 bit product.

     uummuull112288() multiplies its two 64 bit arguments, computing 
_x_*_y, and returns
     the 128 bit product.

     uummuull112288hhii() multiplies its two 64 bit arguments and 
returns the high
     order 64 bits of their 128 bit product. In effect it computes 
_(_x_*_y_)_>_>_6_4
     with 128 bits of intermediate precision.

     uuddiivv6644() divides its 64 bit argument _n_u_m by its 32 bit 
argument _d_e_n_o_m and
     returns the resulting 32 bit quotient and remainder. It is the
     responsibility of the caller to ensure that the result of the operation
     does not overflow the 32 bit quotient, otherwise the returned values are
     undefined.

     uuddiivv112288() divides its 128 bit argument _n_u_m by its 64 
bit argument _d_e_n_o_m
     and returns the resulting 64 bit quotient and remainder. It is the
     responsiblity of the caller to ensure that the result of the operation
     does not overflow the 64 bit quotient, otherwise the returned values are
     undefined.

IIMMPPLLEEMMEENNTTAATTIIOONN NNOOTTEESS
     All of these functions may be implemented as macros and may be expanded
     inline when a suitably short, efficient instruction sequence is available
     for the underlying hardware. As a result, code which attempts to evaluate
     the address of any of the functions may fail with mysterious errors.
     Should this operation be necessary, or if some other reason exists to
     prefer the use of the actual library functions, the macro definition may
     be removed by performing a

        #undef  function_name

     for the name of each function after the

        #include <ulmath.h>

     but before the function is used.

BBUUGGSS
     Perfectly reasonable return values are available to uuccllzz3322() 
and uuccllzz6644()
     when called with a zero-valued argument (i.e. 32 and 64 respectively),
     but since the instructions available on some machines to perform these
     operations don't (easily) return those values the functions punt these
     cases into undefined-land as well.

NetBSD 5.99.24                  April 12, 2010                  NetBSD 5.99.24