ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libecb/ecb.pod
(Generate patch)

Comparing libecb/ecb.pod (file contents):
Revision 1.76 by root, Mon Jan 20 13:13:56 2020 UTC vs.
Revision 1.105 by root, Fri Mar 25 15:22:17 2022 UTC

10 10
11Its homepage can be found here: 11Its homepage can be found here:
12 12
13 http://software.schmorp.de/pkg/libecb 13 http://software.schmorp.de/pkg/libecb
14 14
15It mainly provides a number of wrappers around GCC built-ins, together 15It mainly provides a number of wrappers around many compiler built-ins,
16with replacement functions for other compilers. In addition to this, 16together with replacement functions for other compilers. In addition
17it provides a number of other lowlevel C utilities, such as endianness 17to this, it provides a number of other low-level C utilities, such as
18detection, byte swapping or bit rotations. 18endianness detection, byte swapping or bit rotations.
19 19
20Or in other words, things that should be built into any standard C system, 20Or in other words, things that should be built into any standard C
21but aren't, implemented as efficient as possible with GCC, and still 21system, but aren't, implemented as efficient as possible with GCC (clang,
22correct with other compilers. 22MSVC...), and still correct with other compilers.
23 23
24More might come. 24More might come.
25 25
26=head2 ABOUT THE HEADER 26=head2 ABOUT THE HEADER
27 27
56is usually implemented as a macro. Specifically, a "bool" in this manual 56is usually implemented as a macro. Specifically, a "bool" in this manual
57refers to any kind of boolean value, not a specific type. 57refers to any kind of boolean value, not a specific type.
58 58
59=head2 TYPES / TYPE SUPPORT 59=head2 TYPES / TYPE SUPPORT
60 60
61ecb.h makes sure that the following types are defined (in the expected way): 61F<ecb.h> makes sure that the following types are defined (in the expected way):
62 62
63 int8_t uint8_ 63 int8_t uint8_
64 int16_t uint16_t 64 int16_t uint16_t
65 int32_t uint32_ 65 int32_t uint32_
66 int64_t uint64_t 66 int64_t uint64_t
80 80
81All the following symbols expand to an expression that can be tested in 81All the following symbols expand to an expression that can be tested in
82preprocessor instructions as well as treated as a boolean (use C<!!> to 82preprocessor instructions as well as treated as a boolean (use C<!!> to
83ensure it's either C<0> or C<1> if you need that). 83ensure it's either C<0> or C<1> if you need that).
84 84
85=over 4 85=over
86 86
87=item ECB_C 87=item ECB_C
88 88
89True if the implementation defines the C<__STDC__> macro to a true value, 89True if the implementation defines the C<__STDC__> macro to a true value,
90while not claiming to be C++. 90while not claiming to be C++, i..e C, but not C++.
91 91
92=item ECB_C99 92=item ECB_C99
93 93
94True if the implementation claims to be compliant to C99 (ISO/IEC 94True if the implementation claims to be compliant to C99 (ISO/IEC
959899:1999) or any later version, while not claiming to be C++. 959899:1999) or any later version, while not claiming to be C++.
110=item ECB_CPP11, ECB_CPP14, ECB_CPP17 110=item ECB_CPP11, ECB_CPP14, ECB_CPP17
111 111
112True if the implementation claims to be compliant to C++11/C++14/C++17 112True if the implementation claims to be compliant to C++11/C++14/C++17
113(ISO/IEC 14882:2011, :2014, :2017) or any later version. 113(ISO/IEC 14882:2011, :2014, :2017) or any later version.
114 114
115Note that many C++20 features will likely have their own feature test
116macros (see e.g. L<http://eel.is/c++draft/cpp.predefined#1.8>).
117
118=item ECB_OPTIMIZE_SIZE
119
120Is C<1> when the compiler optimizes for size, C<0> otherwise. This symbol
121can also be defined before including F<ecb.h>, in which case it will be
122unchanged.
123
115=item ECB_GCC_VERSION (major, minor) 124=item ECB_GCC_VERSION (major, minor)
116 125
117Expands to a true value (suitable for testing in by the preprocessor) 126Expands to a true value (suitable for testing by the preprocessor) if the
118if the compiler used is GNU C and the version is the given version, or 127compiler used is GNU C and the version is the given version, or higher.
119higher.
120 128
121This macro tries to return false on compilers that claim to be GCC 129This macro tries to return false on compilers that claim to be GCC
122compatible but aren't. 130compatible but aren't.
123 131
124=item ECB_EXTERN_C 132=item ECB_EXTERN_C
143 151
144 ECB_EXTERN_C_END 152 ECB_EXTERN_C_END
145 153
146=item ECB_STDFP 154=item ECB_STDFP
147 155
148If this evaluates to a true value (suitable for testing in by the 156If this evaluates to a true value (suitable for testing by the
149preprocessor), then C<float> and C<double> use IEEE 754 single/binary32 157preprocessor), then C<float> and C<double> use IEEE 754 single/binary32
150and double/binary64 representations internally I<and> the endianness of 158and double/binary64 representations internally I<and> the endianness of
151both types match the endianness of C<uint32_t> and C<uint64_t>. 159both types match the endianness of C<uint32_t> and C<uint64_t>.
152 160
153This means you can just copy the bits of a C<float> (or C<double>) to an 161This means you can just copy the bits of a C<float> (or C<double>) to an
155without having to think about format or endianness. 163without having to think about format or endianness.
156 164
157This is true for basically all modern platforms, although F<ecb.h> might 165This is true for basically all modern platforms, although F<ecb.h> might
158not be able to deduce this correctly everywhere and might err on the safe 166not be able to deduce this correctly everywhere and might err on the safe
159side. 167side.
168
169=item ECB_64BIT_NATIVE
170
171Evaluates to a true value (suitable for both preprocessor and C code
172testing) if 64 bit integer types on this architecture are evaluated
173"natively", that is, with similar speeds as 32 bit integers. While 64 bit
174integer support is very common (and in fact required by libecb), 32 bit
175CPUs have to emulate operations on them, so you might want to avoid them.
160 176
161=item ECB_AMD64, ECB_AMD64_X32 177=item ECB_AMD64, ECB_AMD64_X32
162 178
163These two macros are defined to C<1> on the x86_64/amd64 ABI and the X32 179These two macros are defined to C<1> on the x86_64/amd64 ABI and the X32
164ABI, respectively, and undefined elsewhere. 180ABI, respectively, and undefined elsewhere.
171 187
172=back 188=back
173 189
174=head2 MACRO TRICKERY 190=head2 MACRO TRICKERY
175 191
176=over 4 192=over
177 193
178=item ECB_CONCAT (a, b) 194=item ECB_CONCAT (a, b)
179 195
180Expands any macros in C<a> and C<b>, then concatenates the result to form 196Expands any macros in C<a> and C<b>, then concatenates the result to form
181a single token. This is mainly useful to form identifiers from components, 197a single token. This is mainly useful to form identifiers from components,
222declarations must be put before the whole declaration: 238declarations must be put before the whole declaration:
223 239
224 ecb_const int mysqrt (int a); 240 ecb_const int mysqrt (int a);
225 ecb_unused int i; 241 ecb_unused int i;
226 242
227=over 4 243=over
228 244
229=item ecb_unused 245=item ecb_unused
230 246
231Marks a function or a variable as "unused", which simply suppresses a 247Marks a function or a variable as "unused", which simply suppresses a
232warning by GCC when it detects it as unused. This is useful when you e.g. 248warning by the compiler when it detects it as unused. This is useful when
233declare a variable but do not always use it: 249you e.g. declare a variable but do not always use it:
234 250
235 { 251 {
236 ecb_unused int var; 252 ecb_unused int var;
237 253
238 #ifdef SOMECONDITION 254 #ifdef SOMECONDITION
258 274
259Expands either to (a compiler-specific equivalent of) C<static inline> or 275Expands either to (a compiler-specific equivalent of) C<static inline> or
260to just C<static>, if inline isn't supported. It should be used to declare 276to just C<static>, if inline isn't supported. It should be used to declare
261functions that should be inlined, for code size or speed reasons. 277functions that should be inlined, for code size or speed reasons.
262 278
263Example: inline this function, it surely will reduce codesize. 279Example: inline this function, it surely will reduce code size.
264 280
265 ecb_inline int 281 ecb_inline int
266 negmul (int a, int b) 282 negmul (int a, int b)
267 { 283 {
268 return - (a * b); 284 return - (a * b);
368speed-critical times, and keeping it in the cache might be a waste of said 384speed-critical times, and keeping it in the cache might be a waste of said
369cache. 385cache.
370 386
371In addition to placing cold functions together (or at least away from hot 387In addition to placing cold functions together (or at least away from hot
372functions), this knowledge can be used in other ways, for example, the 388functions), this knowledge can be used in other ways, for example, the
373function will be optimised for size, as opposed to speed, and codepaths 389function will be optimised for size, as opposed to speed, and code paths
374leading to calls to those functions can automatically be marked as if 390leading to calls to those functions can automatically be marked as if
375C<ecb_expect_false> had been used to reach them. 391C<ecb_expect_false> had been used to reach them.
376 392
377Good examples for such functions would be error reporting functions, or 393Good examples for such functions would be error reporting functions, or
378functions only called in exceptional or rare cases. 394functions only called in exceptional or rare cases.
406 422
407=back 423=back
408 424
409=head2 OPTIMISATION HINTS 425=head2 OPTIMISATION HINTS
410 426
411=over 4 427=over
412
413=item ECB_OPTIMIZE_SIZE
414
415Is C<1> when the compiler optimizes for size, C<0> otherwise. This symbol
416can also be defined before including F<ecb.h>, in which case it will be
417unchanged.
418 428
419=item bool ecb_is_constant (expr) 429=item bool ecb_is_constant (expr)
420 430
421Returns true iff the expression can be deduced to be a compile-time 431Returns true iff the expression can be deduced to be a compile-time
422constant, and false otherwise. 432constant, and false otherwise.
538never be executed. Apart from suppressing a warning in some cases, this 548never be executed. Apart from suppressing a warning in some cases, this
539function can be used to implement C<ecb_assume> or similar functionality. 549function can be used to implement C<ecb_assume> or similar functionality.
540 550
541=item ecb_prefetch (addr, rw, locality) 551=item ecb_prefetch (addr, rw, locality)
542 552
543Tells the compiler to try to prefetch memory at the given C<addr>ess 553Tells the compiler to try to prefetch memory at the given I<addr>ess
544for either reading (C<rw> = 0) or writing (C<rw> = 1). A C<locality> of 554for either reading (I<rw> = 0) or writing (I<rw> = 1). A I<locality> of
545C<0> means that there will only be one access later, C<3> means that 555C<0> means that there will only be one access later, C<3> means that
546the data will likely be accessed very often, and values in between mean 556the data will likely be accessed very often, and values in between mean
547something... in between. The memory pointed to by the address does not 557something... in between. The memory pointed to by the address does not
548need to be accessible (it could be a null pointer for example), but C<rw> 558need to be accessible (it could be a null pointer for example), but C<rw>
549and C<locality> must be compile-time constants. 559and C<locality> must be compile-time constants.
579 589
580=back 590=back
581 591
582=head2 BIT FIDDLING / BIT WIZARDRY 592=head2 BIT FIDDLING / BIT WIZARDRY
583 593
584=over 4 594=over
585 595
586=item bool ecb_big_endian () 596=item bool ecb_big_endian ()
587 597
588=item bool ecb_little_endian () 598=item bool ecb_little_endian ()
589 599
595 605
596=item int ecb_ctz32 (uint32_t x) 606=item int ecb_ctz32 (uint32_t x)
597 607
598=item int ecb_ctz64 (uint64_t x) 608=item int ecb_ctz64 (uint64_t x)
599 609
610=item int ecb_ctz (T x) [C++]
611
600Returns the index of the least significant bit set in C<x> (or 612Returns the index of the least significant bit set in C<x> (or
601equivalently the number of bits set to 0 before the least significant bit 613equivalently the number of bits set to 0 before the least significant bit
602set), starting from 0. If C<x> is 0 the result is undefined. 614set), starting from 0. If C<x> is 0 the result is undefined.
603 615
604For smaller types than C<uint32_t> you can safely use C<ecb_ctz32>. 616For smaller types than C<uint32_t> you can safely use C<ecb_ctz32>.
605 617
618The overloaded C++ C<ecb_ctz> function supports C<uint8_t>, C<uint16_t>,
619C<uint32_t> and C<uint64_t> types.
620
606For example: 621For example:
607 622
608 ecb_ctz32 (3) = 0 623 ecb_ctz32 (3) = 0
609 ecb_ctz32 (6) = 1 624 ecb_ctz32 (6) = 1
610 625
626=item int ecb_clz32 (uint32_t x)
627
628=item int ecb_clz64 (uint64_t x)
629
630=item int ecb_clz (T x) [C++]
631
632Counts the number of leading zero bits in C<x>. If C<x> is 0 the result is
633undefined.
634
635The overloaded C++ C<ecb_clz> function supports C<uint32_t> and
636C<uint64_t> types only.
637
638It is often simpler to use one of the C<ecb_ld*> functions instead, whoise
639result only depends on the value and not the size of the type.
640
641For example:
642
643 ecb_clz32 (3) = 30
644 ecb_clz32 (6) = 29
645
611=item bool ecb_is_pot32 (uint32_t x) 646=item bool ecb_is_pot32 (uint32_t x)
612 647
613=item bool ecb_is_pot64 (uint32_t x) 648=item bool ecb_is_pot64 (uint32_t x)
614 649
650=item bool ecb_is_pot (T x) [C++]
651
615Returns true iff C<x> is a power of two or C<x == 0>. 652Returns true iff C<x> is a power of two or C<x == 0>.
616 653
617For smaller types than C<uint32_t> you can safely use C<ecb_is_pot32>. 654For smaller types than C<uint32_t> you can safely use C<ecb_is_pot32>.
618 655
656The overloaded C++ C<ecb_is_pot> function supports C<uint8_t>, C<uint16_t>,
657C<uint32_t> and C<uint64_t> types.
658
619=item int ecb_ld32 (uint32_t x) 659=item int ecb_ld32 (uint32_t x)
620 660
621=item int ecb_ld64 (uint64_t x) 661=item int ecb_ld64 (uint64_t x)
662
663=item int ecb_ld64 (T x) [C++]
622 664
623Returns the index of the most significant bit set in C<x>, or the number 665Returns the index of the most significant bit set in C<x>, or the number
624of digits the number requires in binary (so that C<< 2**ld <= x < 666of digits the number requires in binary (so that C<< 2**ld <= x <
6252**(ld+1) >>). If C<x> is 0 the result is undefined. A common use case is 6672**(ld+1) >>). If C<x> is 0 the result is undefined. A common use case is
626to compute the integer binary logarithm, i.e. C<floor (log2 (n))>, for 668to compute the integer binary logarithm, i.e. C<floor (log2 (n))>, for
631the given data type), while C<ecb_ld> returns how many bits the number 673the given data type), while C<ecb_ld> returns how many bits the number
632itself requires. 674itself requires.
633 675
634For smaller types than C<uint32_t> you can safely use C<ecb_ld32>. 676For smaller types than C<uint32_t> you can safely use C<ecb_ld32>.
635 677
678The overloaded C++ C<ecb_ld> function supports C<uint8_t>, C<uint16_t>,
679C<uint32_t> and C<uint64_t> types.
680
636=item int ecb_popcount32 (uint32_t x) 681=item int ecb_popcount32 (uint32_t x)
637 682
638=item int ecb_popcount64 (uint64_t x) 683=item int ecb_popcount64 (uint64_t x)
639 684
685=item int ecb_popcount (T x) [C++]
686
640Returns the number of bits set to 1 in C<x>. 687Returns the number of bits set to 1 in C<x>.
641 688
642For smaller types than C<uint32_t> you can safely use C<ecb_popcount32>. 689For smaller types than C<uint32_t> you can safely use C<ecb_popcount32>.
690
691The overloaded C++ C<ecb_popcount> function supports C<uint8_t>, C<uint16_t>,
692C<uint32_t> and C<uint64_t> types.
643 693
644For example: 694For example:
645 695
646 ecb_popcount32 (7) = 3 696 ecb_popcount32 (7) = 3
647 ecb_popcount32 (255) = 8 697 ecb_popcount32 (255) = 8
650 700
651=item uint16_t ecb_bitrev16 (uint16_t x) 701=item uint16_t ecb_bitrev16 (uint16_t x)
652 702
653=item uint32_t ecb_bitrev32 (uint32_t x) 703=item uint32_t ecb_bitrev32 (uint32_t x)
654 704
705=item T ecb_bitrev (T x) [C++]
706
655Reverses the bits in x, i.e. the MSB becomes the LSB, MSB-1 becomes LSB+1 707Reverses the bits in x, i.e. the MSB becomes the LSB, MSB-1 becomes LSB+1
656and so on. 708and so on.
657 709
710The overloaded C++ C<ecb_bitrev> function supports C<uint8_t>, C<uint16_t> and C<uint32_t> types.
711
658Example: 712Example:
659 713
660 ecb_bitrev8 (0xa7) = 0xea 714 ecb_bitrev8 (0xa7) = 0xea
661 ecb_bitrev32 (0xffcc4411) = 0x882233ff 715 ecb_bitrev32 (0xffcc4411) = 0x882233ff
662 716
717=item T ecb_bitrev (T x) [C++]
718
719Overloaded C++ bitrev function.
720
721C<T> must be one of C<uint8_t>, C<uint16_t> or C<uint32_t>.
722
663=item uint32_t ecb_bswap16 (uint32_t x) 723=item uint32_t ecb_bswap16 (uint32_t x)
664 724
665=item uint32_t ecb_bswap32 (uint32_t x) 725=item uint32_t ecb_bswap32 (uint32_t x)
666 726
667=item uint64_t ecb_bswap64 (uint64_t x) 727=item uint64_t ecb_bswap64 (uint64_t x)
728
729=item T ecb_bswap (T x)
668 730
669These functions return the value of the 16-bit (32-bit, 64-bit) value 731These functions return the value of the 16-bit (32-bit, 64-bit) value
670C<x> after reversing the order of bytes (0x11223344 becomes 0x44332211 in 732C<x> after reversing the order of bytes (0x11223344 becomes 0x44332211 in
671C<ecb_bswap32>). 733C<ecb_bswap32>).
672 734
673=item T ecb_bswap (T x) [C++] 735The overloaded C++ C<ecb_bswap> function supports C<uint8_t>, C<uint16_t>,
674 736C<uint32_t> and C<uint64_t> types.
675For C++, an additional generic bswap function is provided. It supports
676C<uint8_t>, C<uint16_t>, C<uint32_t> and C<uint64_t>.
677 737
678=item uint8_t ecb_rotl8 (uint8_t x, unsigned int count) 738=item uint8_t ecb_rotl8 (uint8_t x, unsigned int count)
679 739
680=item uint16_t ecb_rotl16 (uint16_t x, unsigned int count) 740=item uint16_t ecb_rotl16 (uint16_t x, unsigned int count)
681 741
691 751
692=item uint64_t ecb_rotr64 (uint64_t x, unsigned int count) 752=item uint64_t ecb_rotr64 (uint64_t x, unsigned int count)
693 753
694These two families of functions return the value of C<x> after rotating 754These two families of functions return the value of C<x> after rotating
695all the bits by C<count> positions to the right (C<ecb_rotr>) or left 755all the bits by C<count> positions to the right (C<ecb_rotr>) or left
696(C<ecb_rotl>). 756(C<ecb_rotl>). There are no restrictions on the value C<count>, i.e. both
757zero and values equal or larger than the word width work correctly. Also,
758notwithstanding C<count> being unsigned, negative numbers work and shift
759to the opposite direction.
697 760
698Current GCC versions understand these functions and usually compile them 761Current GCC/clang versions understand these functions and usually compile
699to "optimal" code (e.g. a single C<rol> or a combination of C<shld> on 762them to "optimal" code (e.g. a single C<rol> or a combination of C<shld>
700x86). 763on x86).
764
765=item T ecb_rotl (T x, unsigned int count) [C++]
766
767=item T ecb_rotr (T x, unsigned int count) [C++]
768
769Overloaded C++ rotl/rotr functions.
770
771C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>.
772
773=item uint_fast8_t ecb_gray8_encode (uint_fast8_t b)
774
775=item uint_fast16_t ecb_gray16_encode (uint_fast16_t b)
776
777=item uint_fast32_t ecb_gray32_encode (uint_fast32_t b)
778
779=item uint_fast64_t ecb_gray64_encode (uint_fast64_t b)
780
781Encode an unsigned into its corresponding (reflective) gray code - the
782kind of gray code meant when just talking about "gray code". These
783functions are very fast and all have identical implementation, so there is
784no need to use a smaller type, as long as your CPU can handle it natively.
785
786=item T ecb_gray_encode (T b) [C++]
787
788Overloaded C++ version of the above, for C<uint{8,16,32,64}_t>.
789
790=item uint_fast8_t ecb_gray8_decode (uint_fast8_t b)
791
792=item uint_fast16_t ecb_gray16_decode (uint_fast16_t b)
793
794=item uint_fast32_t ecb_gray32_decode (uint_fast32_t b)
795
796=item uint_fast64_t ecb_gray64_decode (uint_fast64_t b)
797
798Decode a gray code back into linear index form (the reverse of
799C<ecb_gray*_encode>. Unlike the encode functions, the decode functions
800have higher time complexity for larger types, so it can pay off to use a
801smaller type here.
802
803=item T ecb_gray_decode (T b) [C++]
804
805Overloaded C++ version of the above, for C<uint{8,16,32,64}_t>.
806
807=back
808
809=head2 HILBERT CURVES
810
811These functions deal with (square, pseudo) Hilbert curves. The parameter
812I<order> indicates the size of the square and is specified in bits, that
813means for order C<8>, the coordinates range from C<0>..C<255>, and the
814curve index ranges from C<0>..C<65535>.
815
816The 32 bit variants of these functions map a 32 bit index to two 16 bit
817coordinates, stored in a 32 bit variable, where the high order bits are
818the x-coordinate, and the low order bits are the y-coordinate, thus,
819these functions map 32 bit linear index on the curve to a 32 bit packed
820coordinate pair, and vice versa.
821
822The 64 bit variants work similarly.
823
824The I<order> can go from C<1> to C<16> for the 32 bit curve, and C<1> to
825C<32> for the 64 bit curve.
826
827When going from one order to the next higher order, these functions
828replace the curve segments by smaller versions of the generating shape,
829while doubling the size (since they use integer coordinates), which is
830what you would expect mathematically. This means that the curve will be
831mirrored at the diagonal. If your goal is to simply cover more area while
832retaining existing point coordinates you should increase or decrease the
833I<order> by C<2> or, in the case of C<ecb_hilbert2d_index_to_coord>,
834simply specify the maximum I<order> of C<16> or C<32>, respectively, as
835these are constant-time.
836
837=over
838
839=item uint32_t ecb_hilbert2d_index_to_coord32 (int order, uint32_t index)
840
841=item uint64_t ecb_hilbert2d_index_to_coord64 (int order, uint64_t index)
842
843Map a point on a pseudo Hilbert curve from its linear distance from the
844origin on the curve to a x|y coordinate pair. The result is a packed
845coordinate pair, to get the actual x and < coordinates, you could do
846something like this:
847
848 uint32_t xy = ecb_hilbert2d_index_to_coord32 (16, 255);
849 uint16_t x = xy >> 16;
850 uint16_t y = xy & 0xffffU;
851
852 uint64_t xy = ecb_hilbert2d_index_to_coord64 (32, 255);
853 uint32_t x = xy >> 32;
854 uint32_t y = xy & 0xffffffffU;
855
856These functions work in constant time, so for many applications it is
857preferable to simply hard-code the order to the maximum (C<16> or C<32>).
858
859This (production-ready, i.e. never run) example generates an SVG image of
860an order 8 pseudo Hilbert curve:
861
862 printf ("<svg xmlns='http://www.w3.org/2000/svg' width='%d' height='%d'>\n", 64 * 8, 64 * 8);
863 printf ("<g transform='translate(4) scale(8)' stroke-width='0.25' stroke='black'>\n");
864 for (uint32_t i = 0; i < 64*64 - 1; ++i)
865 {
866 uint32_t p1 = ecb_hilbert2d_index_to_coord32 (6, i );
867 uint32_t p2 = ecb_hilbert2d_index_to_coord32 (6, i + 1);
868 printf ("<line x1='%d' y1='%d' x2='%d' y2='%d'/>\n",
869 p1 >> 16, p1 & 0xffff,
870 p2 >> 16, p2 & 0xffff);
871 }
872 printf ("</g>\n");
873 printf ("</svg>\n");
874
875=item uint32_t ecb_hilbert2d_coord_to_index32 (int order, uint32_t xy)
876
877=item uint64_t ecb_hilbert2d_coord_to_index64 (int order, uint64_t xy)
878
879The reverse of C<ecb_hilbert2d_index_to_coord> - map a packed pair of
880coordinates to their linear index on the pseudo Hilbert curve of order
881I<order>.
882
883They are an exact inverse of the C<ecb_hilbert2d_coord_to_index> functions
884for the same I<order>:
885
886 assert (
887 u == ecb_hilbert2d_coord_to_index (32,
888 ecb_hilbert2d_index_to_coord32 (32,
889 u)));
890
891Packing coordinates is done the same way, as well, from I<x> and I<y>:
892
893 uint32_t xy = ((uint32_t)x << 16) | y; // for ecb_hilbert2d_coord_to_index32
894 uint64_t xy = ((uint64_t)x << 32) | y; // for ecb_hilbert2d_coord_to_index64
895
896Unlike C<ecb_hilbert2d_coord_to_index>, these functions are O(I<order>),
897so it is preferable to use the lowest possible order.
898
899=back
900
901=head2 BIT MIXING, HASHING
902
903Sometimes you have an integer and want to distribute its bits well, for
904example, to use it as a hash in a hash table. A common example is pointer
905values, which often only have a limited range (e.g. low and high bits are
906often zero).
907
908The following functions try to mix the bits to get a good bias-free
909distribution. They were mainly made for pointers, but the underlying
910integer functions are exposed as well.
911
912As an added benefit, the functions are reversible, so if you find it
913convenient to store only the hash value, you can recover the original
914pointer from the hash ("unmix"), as long as your pointers are 32 or 64 bit
915(if this isn't the case on your platform, drop us a note and we will add
916functions for other bit widths).
917
918The unmix functions are very slightly slower than the mix functions, so
919it is equally very slightly preferable to store the original values wehen
920convenient.
921
922The underlying algorithm if subject to change, so currently these
923functions are not suitable for persistent hash tables, as their result
924value can change between different versions of libecb.
925
926=over
927
928=item uintptr_t ecb_ptrmix (void *ptr)
929
930Mixes the bits of a pointer so the result is suitable for hash table
931lookups. In other words, this hashes the pointer value.
932
933=item uintptr_t ecb_ptrmix (T *ptr) [C++]
934
935Overload the C<ecb_ptrmix> function to work for any pointer in C++.
936
937=item void *ecb_ptrunmix (uintptr_t v)
938
939Unmix the hash value into the original pointer. This only works as long
940as the hash value is not truncated, i.e. you used C<uintptr_t> (or
941equivalent) throughout to store it.
942
943=item T *ecb_ptrunmix<T> (uintptr_t v) [C++]
944
945The somewhat less useful template version of C<ecb_ptrunmix> for
946C++. Example:
947
948 sometype *myptr;
949 uintptr_t hash = ecb_ptrmix (myptr);
950 sometype *orig = ecb_ptrunmix<sometype> (hash);
951
952=item uint32_t ecb_mix32 (uint32_t v)
953
954=item uint64_t ecb_mix64 (uint64_t v)
955
956Sometimes you don't have a pointer but an integer whose values are very
957badly distributed. In this case you can use these integer versions of the
958mixing function. No C++ template is provided currently.
959
960=item uint32_t ecb_unmix32 (uint32_t v)
961
962=item uint64_t ecb_unmix64 (uint64_t v)
963
964The reverse of the C<ecb_mix> functions - they take a mixed/hashed value
965and recover the original value.
701 966
702=back 967=back
703 968
704=head2 HOST ENDIANNESS CONVERSION 969=head2 HOST ENDIANNESS CONVERSION
705 970
706=over 4 971=over
707 972
708=item uint_fast16_t ecb_be_u16_to_host (uint_fast16_t v) 973=item uint_fast16_t ecb_be_u16_to_host (uint_fast16_t v)
709 974
710=item uint_fast32_t ecb_be_u32_to_host (uint_fast32_t v) 975=item uint_fast32_t ecb_be_u32_to_host (uint_fast32_t v)
711 976
718=item uint_fast64_t ecb_le_u64_to_host (uint_fast64_t v) 983=item uint_fast64_t ecb_le_u64_to_host (uint_fast64_t v)
719 984
720Convert an unsigned 16, 32 or 64 bit value from big or little endian to host byte order. 985Convert an unsigned 16, 32 or 64 bit value from big or little endian to host byte order.
721 986
722The naming convention is C<ecb_>(C<be>|C<le>)C<_u>C<16|32|64>C<_to_host>, 987The naming convention is C<ecb_>(C<be>|C<le>)C<_u>C<16|32|64>C<_to_host>,
723where be and le stand for big endian and little endian, respectively. 988where C<be> and C<le> stand for big endian and little endian, respectively.
724 989
725=item uint_fast16_t ecb_host_to_be_u16 (uint_fast16_t v) 990=item uint_fast16_t ecb_host_to_be_u16 (uint_fast16_t v)
726 991
727=item uint_fast32_t ecb_host_to_be_u32 (uint_fast32_t v) 992=item uint_fast32_t ecb_host_to_be_u32 (uint_fast32_t v)
728 993
737Like above, but converts I<from> host byte order to the specified 1002Like above, but converts I<from> host byte order to the specified
738endianness. 1003endianness.
739 1004
740=back 1005=back
741 1006
742In C++ the following additional functions are supported: 1007In C++ the following additional template functions are supported:
743 1008
744=over 4 1009=over
745 1010
746=item T ecb_be_to_host (T v) 1011=item T ecb_be_to_host (T v)
747 1012
748=item T ecb_le_to_host (T v) 1013=item T ecb_le_to_host (T v)
749 1014
750=item T ecb_host_to_be (T v) 1015=item T ecb_host_to_be (T v)
751 1016
752=item T ecb_host_to_le (T v) 1017=item T ecb_host_to_le (T v)
753 1018
1019=back
1020
754These work like their C counterparts, above, but use templates for the 1021These functions work like their C counterparts, above, but use templates,
755type, which make them useful in generic code. 1022which make them useful in generic code.
756 1023
757C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t> 1024C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>
758(so unlike their C counterparts, there is a version for C<uint8_t>, which 1025(so unlike their C counterparts, there is a version for C<uint8_t>, which
759again can be useful in generic code). 1026again can be useful in generic code).
760 1027
761=head2 UNALIGNED LOAD/STORE 1028=head2 UNALIGNED LOAD/STORE
762 1029
763These function load or store unaligned multi-byte values. 1030These function load or store unaligned multi-byte values.
764 1031
765=over 4 1032=over
766 1033
767=item uint_fast16_t ecb_peek_u16_u (const void *ptr) 1034=item uint_fast16_t ecb_peek_u16_u (const void *ptr)
768 1035
769=item uint_fast32_t ecb_peek_u32_u (const void *ptr) 1036=item uint_fast32_t ecb_peek_u32_u (const void *ptr)
770 1037
812Like above, but additionally convert from host byte order to big endian 1079Like above, but additionally convert from host byte order to big endian
813(C<be>) or little endian (C<le>) byte order while doing so. 1080(C<be>) or little endian (C<le>) byte order while doing so.
814 1081
815=back 1082=back
816 1083
817In C++ the following additional functions are supported: 1084In C++ the following additional template functions are supported:
818 1085
819=over 4 1086=over
820 1087
821=item T ecb_peek (const void *ptr) 1088=item T ecb_peek<T> (const void *ptr)
822 1089
823=item T ecb_peek_be (const void *ptr) 1090=item T ecb_peek_be<T> (const void *ptr)
824 1091
825=item T ecb_peek_le (const void *ptr) 1092=item T ecb_peek_le<T> (const void *ptr)
826 1093
827=item T ecb_peek_u (const void *ptr) 1094=item T ecb_peek_u<T> (const void *ptr)
828 1095
829=item T ecb_peek_be_u (const void *ptr) 1096=item T ecb_peek_be_u<T> (const void *ptr)
830 1097
831=item T ecb_peek_le_u (const void *ptr) 1098=item T ecb_peek_le_u<T> (const void *ptr)
832 1099
833Similarly to their C counterparts, these functions load an unsigned 8, 16, 1100Similarly to their C counterparts, these functions load an unsigned 8, 16,
83432 or 64 bit value from memory, with optional conversion from big/little 110132 or 64 bit value from memory, with optional conversion from big/little
835endian. 1102endian.
836 1103
837Since the type cannot be deduced, it has top be specified explicitly, e.g. 1104Since the type cannot be deduced, it has to be specified explicitly, e.g.
838 1105
839 uint_fast16_t v = ecb_peek<uint16_t> (ptr); 1106 uint_fast16_t v = ecb_peek<uint16_t> (ptr);
840 1107
841C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>. 1108C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>.
842 1109
855=item ecb_poke_be_u (void *ptr, T v) 1122=item ecb_poke_be_u (void *ptr, T v)
856 1123
857=item ecb_poke_le_u (void *ptr, T v) 1124=item ecb_poke_le_u (void *ptr, T v)
858 1125
859Again, similarly to their C counterparts, these functions store an 1126Again, similarly to their C counterparts, these functions store an
860unsigned 8, 16, 32 or z64 bit value to memory, with optional conversion to 1127unsigned 8, 16, 32 or 64 bit value to memory, with optional conversion to
861big/little endian. 1128big/little endian.
862 1129
863C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>. 1130C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>.
864 1131
865Unlike their C counterparts, these functions support 8 bit quantities 1132Unlike their C counterparts, these functions support 8 bit quantities
866(C<uint8_t>) and also have an aligned version (without the C<_u> prefix), 1133(C<uint8_t>) and also have an aligned version (without the C<_u> prefix),
867all of which hopefully makes them more useful in generic code. 1134all of which hopefully makes them more useful in generic code.
868 1135
869=back 1136=back
870 1137
1138=head2 FAST INTEGER TO STRING
1139
1140Libecb defines a set of very fast integer to decimal string (or integer
1141to ASCII, short C<i2a>) functions. These work by converting the integer
1142to a fixed point representation and then successively multiplying out
1143the topmost digits. Unlike some other, also very fast, libraries, ecb's
1144algorithm should be completely branchless per digit, and does not rely on
1145the presence of special CPU functions (such as C<clz>).
1146
1147There is a high level API that takes an C<int32_t>, C<uint32_t>,
1148C<int64_t> or C<uint64_t> as argument, and a low-level API, which is
1149harder to use but supports slightly more formatting options.
1150
1151=head3 HIGH LEVEL API
1152
1153The high level API consists of four functions, one each for C<int32_t>,
1154C<uint32_t>, C<int64_t> and C<uint64_t>:
1155
1156Example:
1157
1158 char buf[ECB_I2A_MAX_DIGITS + 1];
1159 char *end = ecb_i2a_i32 (buf, 17262);
1160 *end = 0;
1161 // buf now contains "17262"
1162
1163=over
1164
1165=item ECB_I2A_I32_DIGITS (=11)
1166
1167=item char *ecb_i2a_u32 (char *ptr, uint32_t value)
1168
1169Takes an C<uint32_t> I<value> and formats it as a decimal number starting
1170at I<ptr>, using at most C<ECB_I2A_I32_DIGITS> characters. Returns a
1171pointer to just after the generated string, where you would normally put
1172the terminating C<0> character. This function outputs the minimum number
1173of digits.
1174
1175=item ECB_I2A_U32_DIGITS (=10)
1176
1177=item char *ecb_i2a_i32 (char *ptr, int32_t value)
1178
1179Same as C<ecb_i2a_u32>, but formats a C<int32_t> value, including a minus
1180sign if needed.
1181
1182=item ECB_I2A_I64_DIGITS (=20)
1183
1184=item char *ecb_i2a_u64 (char *ptr, uint64_t value)
1185
1186=item ECB_I2A_U64_DIGITS (=21)
1187
1188=item char *ecb_i2a_i64 (char *ptr, int64_t value)
1189
1190Similar to their 32 bit counterparts, these take a 64 bit argument.
1191
1192=item ECB_I2A_MAX_DIGITS (=21)
1193
1194Instead of using a type specific length macro, you can just use
1195C<ECB_I2A_MAX_DIGITS>, which is good enough for any C<ecb_i2a> function.
1196
1197=back
1198
1199=head3 LOW-LEVEL API
1200
1201The functions above use a number of low-level APIs which have some strict
1202limitations, but can be used as building blocks (studying C<ecb_i2a_i32>
1203and related functions is recommended).
1204
1205There are three families of functions: functions that convert a number
1206to a fixed number of digits with leading zeroes (C<ecb_i2a_0N>, C<0>
1207for "leading zeroes"), functions that generate up to N digits, skipping
1208leading zeroes (C<_N>), and functions that can generate more digits, but
1209the leading digit has limited range (C<_xN>).
1210
1211None of the functions deal with negative numbers.
1212
1213Example: convert an IP address in an C<uint32_t> into dotted-quad:
1214
1215 uint32_t ip = 0x0a000164; // 10.0.1.100
1216 char ips[3 * 4 + 3 + 1];
1217 char *ptr = ips;
1218 ptr = ecb_i2a_3 (ptr, ip >> 24 ); *ptr++ = '.';
1219 ptr = ecb_i2a_3 (ptr, (ip >> 16) & 0xff); *ptr++ = '.';
1220 ptr = ecb_i2a_3 (ptr, (ip >> 8) & 0xff); *ptr++ = '.';
1221 ptr = ecb_i2a_3 (ptr, ip & 0xff); *ptr++ = 0;
1222 printf ("ip: %s\n", ips); // prints "ip: 10.0.1.100"
1223
1224=over
1225
1226=item char *ecb_i2a_02 (char *ptr, uint32_t value) // 32 bit
1227
1228=item char *ecb_i2a_03 (char *ptr, uint32_t value) // 32 bit
1229
1230=item char *ecb_i2a_04 (char *ptr, uint32_t value) // 32 bit
1231
1232=item char *ecb_i2a_05 (char *ptr, uint32_t value) // 64 bit
1233
1234=item char *ecb_i2a_06 (char *ptr, uint32_t value) // 64 bit
1235
1236=item char *ecb_i2a_07 (char *ptr, uint32_t value) // 64 bit
1237
1238=item char *ecb_i2a_08 (char *ptr, uint32_t value) // 64 bit
1239
1240=item char *ecb_i2a_09 (char *ptr, uint32_t value) // 64 bit
1241
1242The C<< ecb_i2a_0I<N> >> functions take an unsigned I<value> and convert
1243them to exactly I<N> digits, returning a pointer to the first character
1244after the digits. The I<value> must be in range. The functions marked with
1245I<32 bit> do their calculations internally in 32 bit, the ones marked with
1246I<64 bit> internally use 64 bit integers, which might be slow on 32 bit
1247architectures (the high level API decides on 32 vs. 64 bit versions using
1248C<ECB_64BIT_NATIVE>).
1249
1250=item char *ecb_i2a_2 (char *ptr, uint32_t value) // 32 bit
1251
1252=item char *ecb_i2a_3 (char *ptr, uint32_t value) // 32 bit
1253
1254=item char *ecb_i2a_4 (char *ptr, uint32_t value) // 32 bit
1255
1256=item char *ecb_i2a_5 (char *ptr, uint32_t value) // 64 bit
1257
1258=item char *ecb_i2a_6 (char *ptr, uint32_t value) // 64 bit
1259
1260=item char *ecb_i2a_7 (char *ptr, uint32_t value) // 64 bit
1261
1262=item char *ecb_i2a_8 (char *ptr, uint32_t value) // 64 bit
1263
1264=item char *ecb_i2a_9 (char *ptr, uint32_t value) // 64 bit
1265
1266Similarly, the C<< ecb_i2a_I<N> >> functions take an unsigned I<value>
1267and convert them to at most I<N> digits, suppressing leading zeroes, and
1268returning a pointer to the first character after the digits.
1269
1270=item ECB_I2A_MAX_X5 (=59074)
1271
1272=item char *ecb_i2a_x5 (char *ptr, uint32_t value) // 32 bit
1273
1274=item ECB_I2A_MAX_X10 (=2932500665)
1275
1276=item char *ecb_i2a_x10 (char *ptr, uint32_t value) // 64 bit
1277
1278The C<< ecb_i2a_xI<N> >> functions are similar to the C<< ecb_i2a_I<N> >>
1279functions, but they can generate one digit more, as long as the number
1280is within range, which is given by the symbols C<ECB_I2A_MAX_X5> (almost
128116 bit range) and C<ECB_I2A_MAX_X10> (a bit more than 31 bit range),
1282respectively.
1283
1284For example, the digit part of a 32 bit signed integer just fits into the
1285C<ECB_I2A_MAX_X10> range, so while C<ecb_i2a_x10> cannot convert a 10
1286digit number, it can convert all 32 bit signed numbers. Sadly, it's not
1287good enough for 32 bit unsigned numbers.
1288
1289=back
1290
871=head2 FLOATING POINT FIDDLING 1291=head2 FLOATING POINT FIDDLING
872 1292
873=over 4 1293=over
874 1294
875=item ECB_INFINITY [-UECB_NO_LIBM] 1295=item ECB_INFINITY [-UECB_NO_LIBM]
876 1296
877Evaluates to positive infinity if supported by the platform, otherwise to 1297Evaluates to positive infinity if supported by the platform, otherwise to
878a truly huge number. 1298a truly huge number.
903IEEE compliant, of course at a speed and code size penalty, and of course 1323IEEE compliant, of course at a speed and code size penalty, and of course
904also within reasonable limits (it tries to convert NaNs, infinities and 1324also within reasonable limits (it tries to convert NaNs, infinities and
905denormals, but will likely convert negative zero to positive zero). 1325denormals, but will likely convert negative zero to positive zero).
906 1326
907On all modern platforms (where C<ECB_STDFP> is true), the compiler should 1327On all modern platforms (where C<ECB_STDFP> is true), the compiler should
908be able to optimise away this function completely. 1328be able to completely optimise away the 32 and 64 bit functions.
909 1329
910These functions can be helpful when serialising floats to the network - you 1330These functions can be helpful when serialising floats to the network - you
911can serialise the return value like a normal uint16_t/uint32_t/uint64_t. 1331can serialise the return value like a normal uint16_t/uint32_t/uint64_t.
912 1332
913Another use for these functions is to manipulate floating point values 1333Another use for these functions is to manipulate floating point values
956 1376
957=back 1377=back
958 1378
959=head2 ARITHMETIC 1379=head2 ARITHMETIC
960 1380
961=over 4 1381=over
962 1382
963=item x = ecb_mod (m, n) 1383=item x = ecb_mod (m, n)
964 1384
965Returns C<m> modulo C<n>, which is the same as the positive remainder 1385Returns C<m> modulo C<n>, which is the same as the positive remainder
966of the division operation between C<m> and C<n>, using floored 1386of the division operation between C<m> and C<n>, using floored
973C<n> must be strictly positive (i.e. C<< >= 1 >>), while C<m> must be 1393C<n> must be strictly positive (i.e. C<< >= 1 >>), while C<m> must be
974negatable, that is, both C<m> and C<-m> must be representable in its 1394negatable, that is, both C<m> and C<-m> must be representable in its
975type (this typically excludes the minimum signed integer value, the same 1395type (this typically excludes the minimum signed integer value, the same
976limitation as for C</> and C<%> in C). 1396limitation as for C</> and C<%> in C).
977 1397
978Current GCC versions compile this into an efficient branchless sequence on 1398Current GCC/clang versions compile this into an efficient branchless
979almost all CPUs. 1399sequence on almost all CPUs.
980 1400
981For example, when you want to rotate forward through the members of an 1401For example, when you want to rotate forward through the members of an
982array for increasing C<m> (which might be negative), then you should use 1402array for increasing C<m> (which might be negative), then you should use
983C<ecb_mod>, as the C<%> operator might give either negative results, or 1403C<ecb_mod>, as the C<%> operator might give either negative results, or
984change direction for negative values: 1404change direction for negative values:
997 1417
998=back 1418=back
999 1419
1000=head2 UTILITY 1420=head2 UTILITY
1001 1421
1002=over 4 1422=over
1003 1423
1004=item element_count = ecb_array_length (name) 1424=item element_count = ecb_array_length (name)
1005 1425
1006Returns the number of elements in the array C<name>. For example: 1426Returns the number of elements in the array C<name>. For example:
1007 1427
1015 1435
1016=head2 SYMBOLS GOVERNING COMPILATION OF ECB.H ITSELF 1436=head2 SYMBOLS GOVERNING COMPILATION OF ECB.H ITSELF
1017 1437
1018These symbols need to be defined before including F<ecb.h> the first time. 1438These symbols need to be defined before including F<ecb.h> the first time.
1019 1439
1020=over 4 1440=over
1021 1441
1022=item ECB_NO_THREADS 1442=item ECB_NO_THREADS
1023 1443
1024If F<ecb.h> is never used from multiple threads, then this symbol can 1444If F<ecb.h> is never used from multiple threads, then this symbol can
1025be defined, in which case memory fences (and similar constructs) are 1445be defined, in which case memory fences (and similar constructs) are
1029 1449
1030=item ECB_NO_SMP 1450=item ECB_NO_SMP
1031 1451
1032The weaker version of C<ECB_NO_THREADS> - if F<ecb.h> is used from 1452The weaker version of C<ECB_NO_THREADS> - if F<ecb.h> is used from
1033multiple threads, but never concurrently (e.g. if the system the program 1453multiple threads, but never concurrently (e.g. if the system the program
1034runs on has only a single CPU with a single core, no hyperthreading and so 1454runs on has only a single CPU with a single core, no hyper-threading and so
1035on), then this symbol can be defined, leading to more efficient code and 1455on), then this symbol can be defined, leading to more efficient code and
1036fewer dependencies. 1456fewer dependencies.
1037 1457
1038=item ECB_NO_LIBM 1458=item ECB_NO_LIBM
1039 1459
1049intended to be internal-use only, some of which we forgot to document, and 1469intended to be internal-use only, some of which we forgot to document, and
1050some of which we hide because we are not sure we will keep the interface 1470some of which we hide because we are not sure we will keep the interface
1051stable. 1471stable.
1052 1472
1053While you are welcome to rummage around and use whatever you find useful 1473While you are welcome to rummage around and use whatever you find useful
1054(we can't stop you), keep in mind that we will change undocumented 1474(we don't want to stop you), keep in mind that we will change undocumented
1055functionality in incompatible ways without thinking twice, while we are 1475functionality in incompatible ways without thinking twice, while we are
1056considerably more conservative with documented things. 1476considerably more conservative with documented things.
1057 1477
1058=head1 AUTHORS 1478=head1 AUTHORS
1059 1479
1060C<libecb> is designed and maintained by: 1480C<libecb> is designed and maintained by:
1061 1481
1062 Emanuele Giaquinta <e.giaquinta@glauco.it> 1482 Emanuele Giaquinta <e.giaquinta@glauco.it>
1063 Marc Alexander Lehmann <schmorp@schmorp.de> 1483 Marc Alexander Lehmann <schmorp@schmorp.de>
1064
1065

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines