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.106 by root, Fri Mar 25 15:23:14 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
630Counts the number of leading zero bits in C<x>. If C<x> is 0 the result is
631undefined.
632
633It is often simpler to use one of the C<ecb_ld*> functions instead, whose
634result only depends on the value and not the size of the type. This is
635also the reason why there is no C++ overload.
636
637For example:
638
639 ecb_clz32 (3) = 30
640 ecb_clz32 (6) = 29
641
611=item bool ecb_is_pot32 (uint32_t x) 642=item bool ecb_is_pot32 (uint32_t x)
612 643
613=item bool ecb_is_pot64 (uint32_t x) 644=item bool ecb_is_pot64 (uint32_t x)
614 645
646=item bool ecb_is_pot (T x) [C++]
647
615Returns true iff C<x> is a power of two or C<x == 0>. 648Returns true iff C<x> is a power of two or C<x == 0>.
616 649
617For smaller types than C<uint32_t> you can safely use C<ecb_is_pot32>. 650For smaller types than C<uint32_t> you can safely use C<ecb_is_pot32>.
618 651
652The overloaded C++ C<ecb_is_pot> function supports C<uint8_t>, C<uint16_t>,
653C<uint32_t> and C<uint64_t> types.
654
619=item int ecb_ld32 (uint32_t x) 655=item int ecb_ld32 (uint32_t x)
620 656
621=item int ecb_ld64 (uint64_t x) 657=item int ecb_ld64 (uint64_t x)
658
659=item int ecb_ld64 (T x) [C++]
622 660
623Returns the index of the most significant bit set in C<x>, or the number 661Returns 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 < 662of 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 6632**(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 664to 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 669the given data type), while C<ecb_ld> returns how many bits the number
632itself requires. 670itself requires.
633 671
634For smaller types than C<uint32_t> you can safely use C<ecb_ld32>. 672For smaller types than C<uint32_t> you can safely use C<ecb_ld32>.
635 673
674The overloaded C++ C<ecb_ld> function supports C<uint8_t>, C<uint16_t>,
675C<uint32_t> and C<uint64_t> types.
676
636=item int ecb_popcount32 (uint32_t x) 677=item int ecb_popcount32 (uint32_t x)
637 678
638=item int ecb_popcount64 (uint64_t x) 679=item int ecb_popcount64 (uint64_t x)
639 680
681=item int ecb_popcount (T x) [C++]
682
640Returns the number of bits set to 1 in C<x>. 683Returns the number of bits set to 1 in C<x>.
641 684
642For smaller types than C<uint32_t> you can safely use C<ecb_popcount32>. 685For smaller types than C<uint32_t> you can safely use C<ecb_popcount32>.
686
687The overloaded C++ C<ecb_popcount> function supports C<uint8_t>, C<uint16_t>,
688C<uint32_t> and C<uint64_t> types.
643 689
644For example: 690For example:
645 691
646 ecb_popcount32 (7) = 3 692 ecb_popcount32 (7) = 3
647 ecb_popcount32 (255) = 8 693 ecb_popcount32 (255) = 8
650 696
651=item uint16_t ecb_bitrev16 (uint16_t x) 697=item uint16_t ecb_bitrev16 (uint16_t x)
652 698
653=item uint32_t ecb_bitrev32 (uint32_t x) 699=item uint32_t ecb_bitrev32 (uint32_t x)
654 700
701=item T ecb_bitrev (T x) [C++]
702
655Reverses the bits in x, i.e. the MSB becomes the LSB, MSB-1 becomes LSB+1 703Reverses the bits in x, i.e. the MSB becomes the LSB, MSB-1 becomes LSB+1
656and so on. 704and so on.
657 705
706The overloaded C++ C<ecb_bitrev> function supports C<uint8_t>, C<uint16_t> and C<uint32_t> types.
707
658Example: 708Example:
659 709
660 ecb_bitrev8 (0xa7) = 0xea 710 ecb_bitrev8 (0xa7) = 0xea
661 ecb_bitrev32 (0xffcc4411) = 0x882233ff 711 ecb_bitrev32 (0xffcc4411) = 0x882233ff
662 712
713=item T ecb_bitrev (T x) [C++]
714
715Overloaded C++ bitrev function.
716
717C<T> must be one of C<uint8_t>, C<uint16_t> or C<uint32_t>.
718
663=item uint32_t ecb_bswap16 (uint32_t x) 719=item uint32_t ecb_bswap16 (uint32_t x)
664 720
665=item uint32_t ecb_bswap32 (uint32_t x) 721=item uint32_t ecb_bswap32 (uint32_t x)
666 722
667=item uint64_t ecb_bswap64 (uint64_t x) 723=item uint64_t ecb_bswap64 (uint64_t x)
724
725=item T ecb_bswap (T x)
668 726
669These functions return the value of the 16-bit (32-bit, 64-bit) value 727These 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 728C<x> after reversing the order of bytes (0x11223344 becomes 0x44332211 in
671C<ecb_bswap32>). 729C<ecb_bswap32>).
672 730
673=item T ecb_bswap (T x) [C++] 731The overloaded C++ C<ecb_bswap> function supports C<uint8_t>, C<uint16_t>,
674 732C<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 733
678=item uint8_t ecb_rotl8 (uint8_t x, unsigned int count) 734=item uint8_t ecb_rotl8 (uint8_t x, unsigned int count)
679 735
680=item uint16_t ecb_rotl16 (uint16_t x, unsigned int count) 736=item uint16_t ecb_rotl16 (uint16_t x, unsigned int count)
681 737
691 747
692=item uint64_t ecb_rotr64 (uint64_t x, unsigned int count) 748=item uint64_t ecb_rotr64 (uint64_t x, unsigned int count)
693 749
694These two families of functions return the value of C<x> after rotating 750These 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 751all the bits by C<count> positions to the right (C<ecb_rotr>) or left
696(C<ecb_rotl>). 752(C<ecb_rotl>). There are no restrictions on the value C<count>, i.e. both
753zero and values equal or larger than the word width work correctly. Also,
754notwithstanding C<count> being unsigned, negative numbers work and shift
755to the opposite direction.
697 756
698Current GCC versions understand these functions and usually compile them 757Current 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 758them to "optimal" code (e.g. a single C<rol> or a combination of C<shld>
700x86). 759on x86).
760
761=item T ecb_rotl (T x, unsigned int count) [C++]
762
763=item T ecb_rotr (T x, unsigned int count) [C++]
764
765Overloaded C++ rotl/rotr functions.
766
767C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>.
768
769=item uint_fast8_t ecb_gray8_encode (uint_fast8_t b)
770
771=item uint_fast16_t ecb_gray16_encode (uint_fast16_t b)
772
773=item uint_fast32_t ecb_gray32_encode (uint_fast32_t b)
774
775=item uint_fast64_t ecb_gray64_encode (uint_fast64_t b)
776
777Encode an unsigned into its corresponding (reflective) gray code - the
778kind of gray code meant when just talking about "gray code". These
779functions are very fast and all have identical implementation, so there is
780no need to use a smaller type, as long as your CPU can handle it natively.
781
782=item T ecb_gray_encode (T b) [C++]
783
784Overloaded C++ version of the above, for C<uint{8,16,32,64}_t>.
785
786=item uint_fast8_t ecb_gray8_decode (uint_fast8_t b)
787
788=item uint_fast16_t ecb_gray16_decode (uint_fast16_t b)
789
790=item uint_fast32_t ecb_gray32_decode (uint_fast32_t b)
791
792=item uint_fast64_t ecb_gray64_decode (uint_fast64_t b)
793
794Decode a gray code back into linear index form (the reverse of
795C<ecb_gray*_encode>. Unlike the encode functions, the decode functions
796have higher time complexity for larger types, so it can pay off to use a
797smaller type here.
798
799=item T ecb_gray_decode (T b) [C++]
800
801Overloaded C++ version of the above, for C<uint{8,16,32,64}_t>.
802
803=back
804
805=head2 HILBERT CURVES
806
807These functions deal with (square, pseudo) Hilbert curves. The parameter
808I<order> indicates the size of the square and is specified in bits, that
809means for order C<8>, the coordinates range from C<0>..C<255>, and the
810curve index ranges from C<0>..C<65535>.
811
812The 32 bit variants of these functions map a 32 bit index to two 16 bit
813coordinates, stored in a 32 bit variable, where the high order bits are
814the x-coordinate, and the low order bits are the y-coordinate, thus,
815these functions map 32 bit linear index on the curve to a 32 bit packed
816coordinate pair, and vice versa.
817
818The 64 bit variants work similarly.
819
820The I<order> can go from C<1> to C<16> for the 32 bit curve, and C<1> to
821C<32> for the 64 bit curve.
822
823When going from one order to the next higher order, these functions
824replace the curve segments by smaller versions of the generating shape,
825while doubling the size (since they use integer coordinates), which is
826what you would expect mathematically. This means that the curve will be
827mirrored at the diagonal. If your goal is to simply cover more area while
828retaining existing point coordinates you should increase or decrease the
829I<order> by C<2> or, in the case of C<ecb_hilbert2d_index_to_coord>,
830simply specify the maximum I<order> of C<16> or C<32>, respectively, as
831these are constant-time.
832
833=over
834
835=item uint32_t ecb_hilbert2d_index_to_coord32 (int order, uint32_t index)
836
837=item uint64_t ecb_hilbert2d_index_to_coord64 (int order, uint64_t index)
838
839Map a point on a pseudo Hilbert curve from its linear distance from the
840origin on the curve to a x|y coordinate pair. The result is a packed
841coordinate pair, to get the actual x and < coordinates, you could do
842something like this:
843
844 uint32_t xy = ecb_hilbert2d_index_to_coord32 (16, 255);
845 uint16_t x = xy >> 16;
846 uint16_t y = xy & 0xffffU;
847
848 uint64_t xy = ecb_hilbert2d_index_to_coord64 (32, 255);
849 uint32_t x = xy >> 32;
850 uint32_t y = xy & 0xffffffffU;
851
852These functions work in constant time, so for many applications it is
853preferable to simply hard-code the order to the maximum (C<16> or C<32>).
854
855This (production-ready, i.e. never run) example generates an SVG image of
856an order 8 pseudo Hilbert curve:
857
858 printf ("<svg xmlns='http://www.w3.org/2000/svg' width='%d' height='%d'>\n", 64 * 8, 64 * 8);
859 printf ("<g transform='translate(4) scale(8)' stroke-width='0.25' stroke='black'>\n");
860 for (uint32_t i = 0; i < 64*64 - 1; ++i)
861 {
862 uint32_t p1 = ecb_hilbert2d_index_to_coord32 (6, i );
863 uint32_t p2 = ecb_hilbert2d_index_to_coord32 (6, i + 1);
864 printf ("<line x1='%d' y1='%d' x2='%d' y2='%d'/>\n",
865 p1 >> 16, p1 & 0xffff,
866 p2 >> 16, p2 & 0xffff);
867 }
868 printf ("</g>\n");
869 printf ("</svg>\n");
870
871=item uint32_t ecb_hilbert2d_coord_to_index32 (int order, uint32_t xy)
872
873=item uint64_t ecb_hilbert2d_coord_to_index64 (int order, uint64_t xy)
874
875The reverse of C<ecb_hilbert2d_index_to_coord> - map a packed pair of
876coordinates to their linear index on the pseudo Hilbert curve of order
877I<order>.
878
879They are an exact inverse of the C<ecb_hilbert2d_coord_to_index> functions
880for the same I<order>:
881
882 assert (
883 u == ecb_hilbert2d_coord_to_index (32,
884 ecb_hilbert2d_index_to_coord32 (32,
885 u)));
886
887Packing coordinates is done the same way, as well, from I<x> and I<y>:
888
889 uint32_t xy = ((uint32_t)x << 16) | y; // for ecb_hilbert2d_coord_to_index32
890 uint64_t xy = ((uint64_t)x << 32) | y; // for ecb_hilbert2d_coord_to_index64
891
892Unlike C<ecb_hilbert2d_coord_to_index>, these functions are O(I<order>),
893so it is preferable to use the lowest possible order.
894
895=back
896
897=head2 BIT MIXING, HASHING
898
899Sometimes you have an integer and want to distribute its bits well, for
900example, to use it as a hash in a hash table. A common example is pointer
901values, which often only have a limited range (e.g. low and high bits are
902often zero).
903
904The following functions try to mix the bits to get a good bias-free
905distribution. They were mainly made for pointers, but the underlying
906integer functions are exposed as well.
907
908As an added benefit, the functions are reversible, so if you find it
909convenient to store only the hash value, you can recover the original
910pointer from the hash ("unmix"), as long as your pointers are 32 or 64 bit
911(if this isn't the case on your platform, drop us a note and we will add
912functions for other bit widths).
913
914The unmix functions are very slightly slower than the mix functions, so
915it is equally very slightly preferable to store the original values wehen
916convenient.
917
918The underlying algorithm if subject to change, so currently these
919functions are not suitable for persistent hash tables, as their result
920value can change between different versions of libecb.
921
922=over
923
924=item uintptr_t ecb_ptrmix (void *ptr)
925
926Mixes the bits of a pointer so the result is suitable for hash table
927lookups. In other words, this hashes the pointer value.
928
929=item uintptr_t ecb_ptrmix (T *ptr) [C++]
930
931Overload the C<ecb_ptrmix> function to work for any pointer in C++.
932
933=item void *ecb_ptrunmix (uintptr_t v)
934
935Unmix the hash value into the original pointer. This only works as long
936as the hash value is not truncated, i.e. you used C<uintptr_t> (or
937equivalent) throughout to store it.
938
939=item T *ecb_ptrunmix<T> (uintptr_t v) [C++]
940
941The somewhat less useful template version of C<ecb_ptrunmix> for
942C++. Example:
943
944 sometype *myptr;
945 uintptr_t hash = ecb_ptrmix (myptr);
946 sometype *orig = ecb_ptrunmix<sometype> (hash);
947
948=item uint32_t ecb_mix32 (uint32_t v)
949
950=item uint64_t ecb_mix64 (uint64_t v)
951
952Sometimes you don't have a pointer but an integer whose values are very
953badly distributed. In this case you can use these integer versions of the
954mixing function. No C++ template is provided currently.
955
956=item uint32_t ecb_unmix32 (uint32_t v)
957
958=item uint64_t ecb_unmix64 (uint64_t v)
959
960The reverse of the C<ecb_mix> functions - they take a mixed/hashed value
961and recover the original value.
701 962
702=back 963=back
703 964
704=head2 HOST ENDIANNESS CONVERSION 965=head2 HOST ENDIANNESS CONVERSION
705 966
706=over 4 967=over
707 968
708=item uint_fast16_t ecb_be_u16_to_host (uint_fast16_t v) 969=item uint_fast16_t ecb_be_u16_to_host (uint_fast16_t v)
709 970
710=item uint_fast32_t ecb_be_u32_to_host (uint_fast32_t v) 971=item uint_fast32_t ecb_be_u32_to_host (uint_fast32_t v)
711 972
718=item uint_fast64_t ecb_le_u64_to_host (uint_fast64_t v) 979=item uint_fast64_t ecb_le_u64_to_host (uint_fast64_t v)
719 980
720Convert an unsigned 16, 32 or 64 bit value from big or little endian to host byte order. 981Convert an unsigned 16, 32 or 64 bit value from big or little endian to host byte order.
721 982
722The naming convention is C<ecb_>(C<be>|C<le>)C<_u>C<16|32|64>C<_to_host>, 983The 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. 984where C<be> and C<le> stand for big endian and little endian, respectively.
724 985
725=item uint_fast16_t ecb_host_to_be_u16 (uint_fast16_t v) 986=item uint_fast16_t ecb_host_to_be_u16 (uint_fast16_t v)
726 987
727=item uint_fast32_t ecb_host_to_be_u32 (uint_fast32_t v) 988=item uint_fast32_t ecb_host_to_be_u32 (uint_fast32_t v)
728 989
737Like above, but converts I<from> host byte order to the specified 998Like above, but converts I<from> host byte order to the specified
738endianness. 999endianness.
739 1000
740=back 1001=back
741 1002
742In C++ the following additional functions are supported: 1003In C++ the following additional template functions are supported:
743 1004
744=over 4 1005=over
745 1006
746=item T ecb_be_to_host (T v) 1007=item T ecb_be_to_host (T v)
747 1008
748=item T ecb_le_to_host (T v) 1009=item T ecb_le_to_host (T v)
749 1010
750=item T ecb_host_to_be (T v) 1011=item T ecb_host_to_be (T v)
751 1012
752=item T ecb_host_to_le (T v) 1013=item T ecb_host_to_le (T v)
753 1014
1015=back
1016
754These work like their C counterparts, above, but use templates for the 1017These functions work like their C counterparts, above, but use templates,
755type, which make them useful in generic code. 1018which make them useful in generic code.
756 1019
757C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t> 1020C<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 1021(so unlike their C counterparts, there is a version for C<uint8_t>, which
759again can be useful in generic code). 1022again can be useful in generic code).
760 1023
761=head2 UNALIGNED LOAD/STORE 1024=head2 UNALIGNED LOAD/STORE
762 1025
763These function load or store unaligned multi-byte values. 1026These function load or store unaligned multi-byte values.
764 1027
765=over 4 1028=over
766 1029
767=item uint_fast16_t ecb_peek_u16_u (const void *ptr) 1030=item uint_fast16_t ecb_peek_u16_u (const void *ptr)
768 1031
769=item uint_fast32_t ecb_peek_u32_u (const void *ptr) 1032=item uint_fast32_t ecb_peek_u32_u (const void *ptr)
770 1033
812Like above, but additionally convert from host byte order to big endian 1075Like above, but additionally convert from host byte order to big endian
813(C<be>) or little endian (C<le>) byte order while doing so. 1076(C<be>) or little endian (C<le>) byte order while doing so.
814 1077
815=back 1078=back
816 1079
817In C++ the following additional functions are supported: 1080In C++ the following additional template functions are supported:
818 1081
819=over 4 1082=over
820 1083
821=item T ecb_peek (const void *ptr) 1084=item T ecb_peek<T> (const void *ptr)
822 1085
823=item T ecb_peek_be (const void *ptr) 1086=item T ecb_peek_be<T> (const void *ptr)
824 1087
825=item T ecb_peek_le (const void *ptr) 1088=item T ecb_peek_le<T> (const void *ptr)
826 1089
827=item T ecb_peek_u (const void *ptr) 1090=item T ecb_peek_u<T> (const void *ptr)
828 1091
829=item T ecb_peek_be_u (const void *ptr) 1092=item T ecb_peek_be_u<T> (const void *ptr)
830 1093
831=item T ecb_peek_le_u (const void *ptr) 1094=item T ecb_peek_le_u<T> (const void *ptr)
832 1095
833Similarly to their C counterparts, these functions load an unsigned 8, 16, 1096Similarly to their C counterparts, these functions load an unsigned 8, 16,
83432 or 64 bit value from memory, with optional conversion from big/little 109732 or 64 bit value from memory, with optional conversion from big/little
835endian. 1098endian.
836 1099
837Since the type cannot be deduced, it has top be specified explicitly, e.g. 1100Since the type cannot be deduced, it has to be specified explicitly, e.g.
838 1101
839 uint_fast16_t v = ecb_peek<uint16_t> (ptr); 1102 uint_fast16_t v = ecb_peek<uint16_t> (ptr);
840 1103
841C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>. 1104C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>.
842 1105
855=item ecb_poke_be_u (void *ptr, T v) 1118=item ecb_poke_be_u (void *ptr, T v)
856 1119
857=item ecb_poke_le_u (void *ptr, T v) 1120=item ecb_poke_le_u (void *ptr, T v)
858 1121
859Again, similarly to their C counterparts, these functions store an 1122Again, similarly to their C counterparts, these functions store an
860unsigned 8, 16, 32 or z64 bit value to memory, with optional conversion to 1123unsigned 8, 16, 32 or 64 bit value to memory, with optional conversion to
861big/little endian. 1124big/little endian.
862 1125
863C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>. 1126C<T> must be one of C<uint8_t>, C<uint16_t>, C<uint32_t> or C<uint64_t>.
864 1127
865Unlike their C counterparts, these functions support 8 bit quantities 1128Unlike their C counterparts, these functions support 8 bit quantities
866(C<uint8_t>) and also have an aligned version (without the C<_u> prefix), 1129(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. 1130all of which hopefully makes them more useful in generic code.
868 1131
869=back 1132=back
870 1133
1134=head2 FAST INTEGER TO STRING
1135
1136Libecb defines a set of very fast integer to decimal string (or integer
1137to ASCII, short C<i2a>) functions. These work by converting the integer
1138to a fixed point representation and then successively multiplying out
1139the topmost digits. Unlike some other, also very fast, libraries, ecb's
1140algorithm should be completely branchless per digit, and does not rely on
1141the presence of special CPU functions (such as C<clz>).
1142
1143There is a high level API that takes an C<int32_t>, C<uint32_t>,
1144C<int64_t> or C<uint64_t> as argument, and a low-level API, which is
1145harder to use but supports slightly more formatting options.
1146
1147=head3 HIGH LEVEL API
1148
1149The high level API consists of four functions, one each for C<int32_t>,
1150C<uint32_t>, C<int64_t> and C<uint64_t>:
1151
1152Example:
1153
1154 char buf[ECB_I2A_MAX_DIGITS + 1];
1155 char *end = ecb_i2a_i32 (buf, 17262);
1156 *end = 0;
1157 // buf now contains "17262"
1158
1159=over
1160
1161=item ECB_I2A_I32_DIGITS (=11)
1162
1163=item char *ecb_i2a_u32 (char *ptr, uint32_t value)
1164
1165Takes an C<uint32_t> I<value> and formats it as a decimal number starting
1166at I<ptr>, using at most C<ECB_I2A_I32_DIGITS> characters. Returns a
1167pointer to just after the generated string, where you would normally put
1168the terminating C<0> character. This function outputs the minimum number
1169of digits.
1170
1171=item ECB_I2A_U32_DIGITS (=10)
1172
1173=item char *ecb_i2a_i32 (char *ptr, int32_t value)
1174
1175Same as C<ecb_i2a_u32>, but formats a C<int32_t> value, including a minus
1176sign if needed.
1177
1178=item ECB_I2A_I64_DIGITS (=20)
1179
1180=item char *ecb_i2a_u64 (char *ptr, uint64_t value)
1181
1182=item ECB_I2A_U64_DIGITS (=21)
1183
1184=item char *ecb_i2a_i64 (char *ptr, int64_t value)
1185
1186Similar to their 32 bit counterparts, these take a 64 bit argument.
1187
1188=item ECB_I2A_MAX_DIGITS (=21)
1189
1190Instead of using a type specific length macro, you can just use
1191C<ECB_I2A_MAX_DIGITS>, which is good enough for any C<ecb_i2a> function.
1192
1193=back
1194
1195=head3 LOW-LEVEL API
1196
1197The functions above use a number of low-level APIs which have some strict
1198limitations, but can be used as building blocks (studying C<ecb_i2a_i32>
1199and related functions is recommended).
1200
1201There are three families of functions: functions that convert a number
1202to a fixed number of digits with leading zeroes (C<ecb_i2a_0N>, C<0>
1203for "leading zeroes"), functions that generate up to N digits, skipping
1204leading zeroes (C<_N>), and functions that can generate more digits, but
1205the leading digit has limited range (C<_xN>).
1206
1207None of the functions deal with negative numbers.
1208
1209Example: convert an IP address in an C<uint32_t> into dotted-quad:
1210
1211 uint32_t ip = 0x0a000164; // 10.0.1.100
1212 char ips[3 * 4 + 3 + 1];
1213 char *ptr = ips;
1214 ptr = ecb_i2a_3 (ptr, ip >> 24 ); *ptr++ = '.';
1215 ptr = ecb_i2a_3 (ptr, (ip >> 16) & 0xff); *ptr++ = '.';
1216 ptr = ecb_i2a_3 (ptr, (ip >> 8) & 0xff); *ptr++ = '.';
1217 ptr = ecb_i2a_3 (ptr, ip & 0xff); *ptr++ = 0;
1218 printf ("ip: %s\n", ips); // prints "ip: 10.0.1.100"
1219
1220=over
1221
1222=item char *ecb_i2a_02 (char *ptr, uint32_t value) // 32 bit
1223
1224=item char *ecb_i2a_03 (char *ptr, uint32_t value) // 32 bit
1225
1226=item char *ecb_i2a_04 (char *ptr, uint32_t value) // 32 bit
1227
1228=item char *ecb_i2a_05 (char *ptr, uint32_t value) // 64 bit
1229
1230=item char *ecb_i2a_06 (char *ptr, uint32_t value) // 64 bit
1231
1232=item char *ecb_i2a_07 (char *ptr, uint32_t value) // 64 bit
1233
1234=item char *ecb_i2a_08 (char *ptr, uint32_t value) // 64 bit
1235
1236=item char *ecb_i2a_09 (char *ptr, uint32_t value) // 64 bit
1237
1238The C<< ecb_i2a_0I<N> >> functions take an unsigned I<value> and convert
1239them to exactly I<N> digits, returning a pointer to the first character
1240after the digits. The I<value> must be in range. The functions marked with
1241I<32 bit> do their calculations internally in 32 bit, the ones marked with
1242I<64 bit> internally use 64 bit integers, which might be slow on 32 bit
1243architectures (the high level API decides on 32 vs. 64 bit versions using
1244C<ECB_64BIT_NATIVE>).
1245
1246=item char *ecb_i2a_2 (char *ptr, uint32_t value) // 32 bit
1247
1248=item char *ecb_i2a_3 (char *ptr, uint32_t value) // 32 bit
1249
1250=item char *ecb_i2a_4 (char *ptr, uint32_t value) // 32 bit
1251
1252=item char *ecb_i2a_5 (char *ptr, uint32_t value) // 64 bit
1253
1254=item char *ecb_i2a_6 (char *ptr, uint32_t value) // 64 bit
1255
1256=item char *ecb_i2a_7 (char *ptr, uint32_t value) // 64 bit
1257
1258=item char *ecb_i2a_8 (char *ptr, uint32_t value) // 64 bit
1259
1260=item char *ecb_i2a_9 (char *ptr, uint32_t value) // 64 bit
1261
1262Similarly, the C<< ecb_i2a_I<N> >> functions take an unsigned I<value>
1263and convert them to at most I<N> digits, suppressing leading zeroes, and
1264returning a pointer to the first character after the digits.
1265
1266=item ECB_I2A_MAX_X5 (=59074)
1267
1268=item char *ecb_i2a_x5 (char *ptr, uint32_t value) // 32 bit
1269
1270=item ECB_I2A_MAX_X10 (=2932500665)
1271
1272=item char *ecb_i2a_x10 (char *ptr, uint32_t value) // 64 bit
1273
1274The C<< ecb_i2a_xI<N> >> functions are similar to the C<< ecb_i2a_I<N> >>
1275functions, but they can generate one digit more, as long as the number
1276is within range, which is given by the symbols C<ECB_I2A_MAX_X5> (almost
127716 bit range) and C<ECB_I2A_MAX_X10> (a bit more than 31 bit range),
1278respectively.
1279
1280For example, the digit part of a 32 bit signed integer just fits into the
1281C<ECB_I2A_MAX_X10> range, so while C<ecb_i2a_x10> cannot convert a 10
1282digit number, it can convert all 32 bit signed numbers. Sadly, it's not
1283good enough for 32 bit unsigned numbers.
1284
1285=back
1286
871=head2 FLOATING POINT FIDDLING 1287=head2 FLOATING POINT FIDDLING
872 1288
873=over 4 1289=over
874 1290
875=item ECB_INFINITY [-UECB_NO_LIBM] 1291=item ECB_INFINITY [-UECB_NO_LIBM]
876 1292
877Evaluates to positive infinity if supported by the platform, otherwise to 1293Evaluates to positive infinity if supported by the platform, otherwise to
878a truly huge number. 1294a truly huge number.
903IEEE compliant, of course at a speed and code size penalty, and of course 1319IEEE compliant, of course at a speed and code size penalty, and of course
904also within reasonable limits (it tries to convert NaNs, infinities and 1320also within reasonable limits (it tries to convert NaNs, infinities and
905denormals, but will likely convert negative zero to positive zero). 1321denormals, but will likely convert negative zero to positive zero).
906 1322
907On all modern platforms (where C<ECB_STDFP> is true), the compiler should 1323On all modern platforms (where C<ECB_STDFP> is true), the compiler should
908be able to optimise away this function completely. 1324be able to completely optimise away the 32 and 64 bit functions.
909 1325
910These functions can be helpful when serialising floats to the network - you 1326These 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. 1327can serialise the return value like a normal uint16_t/uint32_t/uint64_t.
912 1328
913Another use for these functions is to manipulate floating point values 1329Another use for these functions is to manipulate floating point values
956 1372
957=back 1373=back
958 1374
959=head2 ARITHMETIC 1375=head2 ARITHMETIC
960 1376
961=over 4 1377=over
962 1378
963=item x = ecb_mod (m, n) 1379=item x = ecb_mod (m, n)
964 1380
965Returns C<m> modulo C<n>, which is the same as the positive remainder 1381Returns 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 1382of 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 1389C<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 1390negatable, that is, both C<m> and C<-m> must be representable in its
975type (this typically excludes the minimum signed integer value, the same 1391type (this typically excludes the minimum signed integer value, the same
976limitation as for C</> and C<%> in C). 1392limitation as for C</> and C<%> in C).
977 1393
978Current GCC versions compile this into an efficient branchless sequence on 1394Current GCC/clang versions compile this into an efficient branchless
979almost all CPUs. 1395sequence on almost all CPUs.
980 1396
981For example, when you want to rotate forward through the members of an 1397For 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 1398array 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 1399C<ecb_mod>, as the C<%> operator might give either negative results, or
984change direction for negative values: 1400change direction for negative values:
997 1413
998=back 1414=back
999 1415
1000=head2 UTILITY 1416=head2 UTILITY
1001 1417
1002=over 4 1418=over
1003 1419
1004=item element_count = ecb_array_length (name) 1420=item element_count = ecb_array_length (name)
1005 1421
1006Returns the number of elements in the array C<name>. For example: 1422Returns the number of elements in the array C<name>. For example:
1007 1423
1015 1431
1016=head2 SYMBOLS GOVERNING COMPILATION OF ECB.H ITSELF 1432=head2 SYMBOLS GOVERNING COMPILATION OF ECB.H ITSELF
1017 1433
1018These symbols need to be defined before including F<ecb.h> the first time. 1434These symbols need to be defined before including F<ecb.h> the first time.
1019 1435
1020=over 4 1436=over
1021 1437
1022=item ECB_NO_THREADS 1438=item ECB_NO_THREADS
1023 1439
1024If F<ecb.h> is never used from multiple threads, then this symbol can 1440If F<ecb.h> is never used from multiple threads, then this symbol can
1025be defined, in which case memory fences (and similar constructs) are 1441be defined, in which case memory fences (and similar constructs) are
1029 1445
1030=item ECB_NO_SMP 1446=item ECB_NO_SMP
1031 1447
1032The weaker version of C<ECB_NO_THREADS> - if F<ecb.h> is used from 1448The 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 1449multiple 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 1450runs 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 1451on), then this symbol can be defined, leading to more efficient code and
1036fewer dependencies. 1452fewer dependencies.
1037 1453
1038=item ECB_NO_LIBM 1454=item ECB_NO_LIBM
1039 1455
1049intended to be internal-use only, some of which we forgot to document, and 1465intended 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 1466some of which we hide because we are not sure we will keep the interface
1051stable. 1467stable.
1052 1468
1053While you are welcome to rummage around and use whatever you find useful 1469While 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 1470(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 1471functionality in incompatible ways without thinking twice, while we are
1056considerably more conservative with documented things. 1472considerably more conservative with documented things.
1057 1473
1058=head1 AUTHORS 1474=head1 AUTHORS
1059 1475
1060C<libecb> is designed and maintained by: 1476C<libecb> is designed and maintained by:
1061 1477
1062 Emanuele Giaquinta <e.giaquinta@glauco.it> 1478 Emanuele Giaquinta <e.giaquinta@glauco.it>
1063 Marc Alexander Lehmann <schmorp@schmorp.de> 1479 Marc Alexander Lehmann <schmorp@schmorp.de>
1064
1065

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines