tech-userlevel archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Long unsigned integer math library
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
Home |
Main Index |
Thread Index |
Old Index