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

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

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines