ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libecb/ecb.pod
Revision: 1.42
Committed: Mon May 28 08:54:03 2012 UTC (12 years, 1 month ago) by root
Branch: MAIN
Changes since 1.41: +3 -3 lines
Log Message:
*** empty log message ***

File Contents

# Content
1 =head1 LIBECB - e-C-Builtins
2
3 =head2 ABOUT LIBECB
4
5 Libecb is currently a simple header file that doesn't require any
6 configuration to use or include in your project.
7
8 It's part of the e-suite of libraries, other members of which include
9 libev and libeio.
10
11 Its homepage can be found here:
12
13 http://software.schmorp.de/pkg/libecb
14
15 It mainly provides a number of wrappers around GCC built-ins, together
16 with replacement functions for other compilers. In addition to this,
17 it provides a number of other lowlevel C utilities, such as endianness
18 detection, byte swapping or bit rotations.
19
20 Or in other words, things that should be built into any standard C system,
21 but aren't, implemented as efficient as possible with GCC, and still
22 correct with other compilers.
23
24 More might come.
25
26 =head2 ABOUT THE HEADER
27
28 At the moment, all you have to do is copy F<ecb.h> somewhere where your
29 compiler can find it and include it:
30
31 #include <ecb.h>
32
33 The header should work fine for both C and C++ compilation, and gives you
34 all of F<inttypes.h> in addition to the ECB symbols.
35
36 There are currently no object files to link to - future versions might
37 come with an (optional) object code library to link against, to reduce
38 code size or gain access to additional features.
39
40 It also currently includes everything from F<inttypes.h>.
41
42 =head2 ABOUT THIS MANUAL / CONVENTIONS
43
44 This manual mainly describes each (public) function available after
45 including the F<ecb.h> header. The header might define other symbols than
46 these, but these are not part of the public API, and not supported in any
47 way.
48
49 When the manual mentions a "function" then this could be defined either as
50 as inline function, a macro, or an external symbol.
51
52 When functions use a concrete standard type, such as C<int> or
53 C<uint32_t>, then the corresponding function works only with that type. If
54 only a generic name is used (C<expr>, C<cond>, C<value> and so on), then
55 the corresponding function relies on C to implement the correct types, and
56 is usually implemented as a macro. Specifically, a "bool" in this manual
57 refers to any kind of boolean value, not a specific type.
58
59 =head2 TYPES / TYPE SUPPORT
60
61 ecb.h makes sure that the following types are defined (in the expected way):
62
63 int8_t uint8_t int16_t uint16_t
64 int32_t uint32_t int64_t uint64_t
65 intptr_t uintptr_t ptrdiff_t
66
67 The macro C<ECB_PTRSIZE> is defined to the size of a pointer on this
68 platform (currently C<4> or C<8>).
69
70 =head2 GCC ATTRIBUTES
71
72 A major part of libecb deals with GCC attributes. These are additional
73 attributes that you can assign to functions, variables and sometimes even
74 types - much like C<const> or C<volatile> in C.
75
76 While GCC allows declarations to show up in many surprising places,
77 but not in many expected places, the safest way is to put attribute
78 declarations before the whole declaration:
79
80 ecb_const int mysqrt (int a);
81 ecb_unused int i;
82
83 For variables, it is often nicer to put the attribute after the name, and
84 avoid multiple declarations using commas:
85
86 int i ecb_unused;
87
88 =over 4
89
90 =item ecb_attribute ((attrs...))
91
92 A simple wrapper that expands to C<__attribute__((attrs))> on GCC, and to
93 nothing on other compilers, so the effect is that only GCC sees these.
94
95 Example: use the C<deprecated> attribute on a function.
96
97 ecb_attribute((__deprecated__)) void
98 do_not_use_me_anymore (void);
99
100 =item ecb_unused
101
102 Marks a function or a variable as "unused", which simply suppresses a
103 warning by GCC when it detects it as unused. This is useful when you e.g.
104 declare a variable but do not always use it:
105
106 {
107 int var ecb_unused;
108
109 #ifdef SOMECONDITION
110 var = ...;
111 return var;
112 #else
113 return 0;
114 #endif
115 }
116
117 =item ecb_inline
118
119 This is not actually an attribute, but you use it like one. It expands
120 either to C<static inline> or to just C<static>, if inline isn't
121 supported. It should be used to declare functions that should be inlined,
122 for code size or speed reasons.
123
124 Example: inline this function, it surely will reduce codesize.
125
126 ecb_inline int
127 negmul (int a, int b)
128 {
129 return - (a * b);
130 }
131
132 =item ecb_noinline
133
134 Prevent a function from being inlined - it might be optimised away, but
135 not inlined into other functions. This is useful if you know your function
136 is rarely called and large enough for inlining not to be helpful.
137
138 =item ecb_noreturn
139
140 Marks a function as "not returning, ever". Some typical functions that
141 don't return are C<exit> or C<abort> (which really works hard to not
142 return), and now you can make your own:
143
144 ecb_noreturn void
145 my_abort (const char *errline)
146 {
147 puts (errline);
148 abort ();
149 }
150
151 In this case, the compiler would probably be smart enough to deduce it on
152 its own, so this is mainly useful for declarations.
153
154 =item ecb_const
155
156 Declares that the function only depends on the values of its arguments,
157 much like a mathematical function. It specifically does not read or write
158 any memory any arguments might point to, global variables, or call any
159 non-const functions. It also must not have any side effects.
160
161 Such a function can be optimised much more aggressively by the compiler -
162 for example, multiple calls with the same arguments can be optimised into
163 a single call, which wouldn't be possible if the compiler would have to
164 expect any side effects.
165
166 It is best suited for functions in the sense of mathematical functions,
167 such as a function returning the square root of its input argument.
168
169 Not suited would be a function that calculates the hash of some memory
170 area you pass in, prints some messages or looks at a global variable to
171 decide on rounding.
172
173 See C<ecb_pure> for a slightly less restrictive class of functions.
174
175 =item ecb_pure
176
177 Similar to C<ecb_const>, declares a function that has no side
178 effects. Unlike C<ecb_const>, the function is allowed to examine global
179 variables and any other memory areas (such as the ones passed to it via
180 pointers).
181
182 While these functions cannot be optimised as aggressively as C<ecb_const>
183 functions, they can still be optimised away in many occasions, and the
184 compiler has more freedom in moving calls to them around.
185
186 Typical examples for such functions would be C<strlen> or C<memcmp>. A
187 function that calculates the MD5 sum of some input and updates some MD5
188 state passed as argument would I<NOT> be pure, however, as it would modify
189 some memory area that is not the return value.
190
191 =item ecb_hot
192
193 This declares a function as "hot" with regards to the cache - the function
194 is used so often, that it is very beneficial to keep it in the cache if
195 possible.
196
197 The compiler reacts by trying to place hot functions near to each other in
198 memory.
199
200 Whether a function is hot or not often depends on the whole program,
201 and less on the function itself. C<ecb_cold> is likely more useful in
202 practise.
203
204 =item ecb_cold
205
206 The opposite of C<ecb_hot> - declares a function as "cold" with regards to
207 the cache, or in other words, this function is not called often, or not at
208 speed-critical times, and keeping it in the cache might be a waste of said
209 cache.
210
211 In addition to placing cold functions together (or at least away from hot
212 functions), this knowledge can be used in other ways, for example, the
213 function will be optimised for size, as opposed to speed, and codepaths
214 leading to calls to those functions can automatically be marked as if
215 C<ecb_expect_false> had been used to reach them.
216
217 Good examples for such functions would be error reporting functions, or
218 functions only called in exceptional or rare cases.
219
220 =item ecb_artificial
221
222 Declares the function as "artificial", in this case meaning that this
223 function is not really mean to be a function, but more like an accessor
224 - many methods in C++ classes are mere accessor functions, and having a
225 crash reported in such a method, or single-stepping through them, is not
226 usually so helpful, especially when it's inlined to just a few instructions.
227
228 Marking them as artificial will instruct the debugger about just this,
229 leading to happier debugging and thus happier lives.
230
231 Example: in some kind of smart-pointer class, mark the pointer accessor as
232 artificial, so that the whole class acts more like a pointer and less like
233 some C++ abstraction monster.
234
235 template<typename T>
236 struct my_smart_ptr
237 {
238 T *value;
239
240 ecb_artificial
241 operator T *()
242 {
243 return value;
244 }
245 };
246
247 =back
248
249 =head2 OPTIMISATION HINTS
250
251 =over 4
252
253 =item bool ecb_is_constant(expr)
254
255 Returns true iff the expression can be deduced to be a compile-time
256 constant, and false otherwise.
257
258 For example, when you have a C<rndm16> function that returns a 16 bit
259 random number, and you have a function that maps this to a range from
260 0..n-1, then you could use this inline function in a header file:
261
262 ecb_inline uint32_t
263 rndm (uint32_t n)
264 {
265 return (n * (uint32_t)rndm16 ()) >> 16;
266 }
267
268 However, for powers of two, you could use a normal mask, but that is only
269 worth it if, at compile time, you can detect this case. This is the case
270 when the passed number is a constant and also a power of two (C<n & (n -
271 1) == 0>):
272
273 ecb_inline uint32_t
274 rndm (uint32_t n)
275 {
276 return is_constant (n) && !(n & (n - 1))
277 ? rndm16 () & (num - 1)
278 : (n * (uint32_t)rndm16 ()) >> 16;
279 }
280
281 =item bool ecb_expect (expr, value)
282
283 Evaluates C<expr> and returns it. In addition, it tells the compiler that
284 the C<expr> evaluates to C<value> a lot, which can be used for static
285 branch optimisations.
286
287 Usually, you want to use the more intuitive C<ecb_expect_true> and
288 C<ecb_expect_false> functions instead.
289
290 =item bool ecb_expect_true (cond)
291
292 =item bool ecb_expect_false (cond)
293
294 These two functions expect a expression that is true or false and return
295 C<1> or C<0>, respectively, so when used in the condition of an C<if> or
296 other conditional statement, it will not change the program:
297
298 /* these two do the same thing */
299 if (some_condition) ...;
300 if (ecb_expect_true (some_condition)) ...;
301
302 However, by using C<ecb_expect_true>, you tell the compiler that the
303 condition is likely to be true (and for C<ecb_expect_false>, that it is
304 unlikely to be true).
305
306 For example, when you check for a null pointer and expect this to be a
307 rare, exceptional, case, then use C<ecb_expect_false>:
308
309 void my_free (void *ptr)
310 {
311 if (ecb_expect_false (ptr == 0))
312 return;
313 }
314
315 Consequent use of these functions to mark away exceptional cases or to
316 tell the compiler what the hot path through a function is can increase
317 performance considerably.
318
319 You might know these functions under the name C<likely> and C<unlikely>
320 - while these are common aliases, we find that the expect name is easier
321 to understand when quickly skimming code. If you wish, you can use
322 C<ecb_likely> instead of C<ecb_expect_true> and C<ecb_unlikely> instead of
323 C<ecb_expect_false> - these are simply aliases.
324
325 A very good example is in a function that reserves more space for some
326 memory block (for example, inside an implementation of a string stream) -
327 each time something is added, you have to check for a buffer overrun, but
328 you expect that most checks will turn out to be false:
329
330 /* make sure we have "size" extra room in our buffer */
331 ecb_inline void
332 reserve (int size)
333 {
334 if (ecb_expect_false (current + size > end))
335 real_reserve_method (size); /* presumably noinline */
336 }
337
338 =item bool ecb_assume (cond)
339
340 Try to tell the compiler that some condition is true, even if it's not
341 obvious.
342
343 This can be used to teach the compiler about invariants or other
344 conditions that might improve code generation, but which are impossible to
345 deduce form the code itself.
346
347 For example, the example reservation function from the C<ecb_expect_false>
348 description could be written thus (only C<ecb_assume> was added):
349
350 ecb_inline void
351 reserve (int size)
352 {
353 if (ecb_expect_false (current + size > end))
354 real_reserve_method (size); /* presumably noinline */
355
356 ecb_assume (current + size <= end);
357 }
358
359 If you then call this function twice, like this:
360
361 reserve (10);
362 reserve (1);
363
364 Then the compiler I<might> be able to optimise out the second call
365 completely, as it knows that C<< current + 1 > end >> is false and the
366 call will never be executed.
367
368 =item bool ecb_unreachable ()
369
370 This function does nothing itself, except tell the compiler that it will
371 never be executed. Apart from suppressing a warning in some cases, this
372 function can be used to implement C<ecb_assume> or similar functions.
373
374 =item bool ecb_prefetch (addr, rw, locality)
375
376 Tells the compiler to try to prefetch memory at the given C<addr>ess
377 for either reading (C<rw> = 0) or writing (C<rw> = 1). A C<locality> of
378 C<0> means that there will only be one access later, C<3> means that
379 the data will likely be accessed very often, and values in between mean
380 something... in between. The memory pointed to by the address does not
381 need to be accessible (it could be a null pointer for example), but C<rw>
382 and C<locality> must be compile-time constants.
383
384 An obvious way to use this is to prefetch some data far away, in a big
385 array you loop over. This prefetches memory some 128 array elements later,
386 in the hope that it will be ready when the CPU arrives at that location.
387
388 int sum = 0;
389
390 for (i = 0; i < N; ++i)
391 {
392 sum += arr [i]
393 ecb_prefetch (arr + i + 128, 0, 0);
394 }
395
396 It's hard to predict how far to prefetch, and most CPUs that can prefetch
397 are often good enough to predict this kind of behaviour themselves. It
398 gets more interesting with linked lists, especially when you do some fair
399 processing on each list element:
400
401 for (node *n = start; n; n = n->next)
402 {
403 ecb_prefetch (n->next, 0, 0);
404 ... do medium amount of work with *n
405 }
406
407 After processing the node, (part of) the next node might already be in
408 cache.
409
410 =back
411
412 =head2 BIT FIDDLING / BIT WIZARDRY
413
414 =over 4
415
416 =item bool ecb_big_endian ()
417
418 =item bool ecb_little_endian ()
419
420 These two functions return true if the byte order is big endian
421 (most-significant byte first) or little endian (least-significant byte
422 first) respectively.
423
424 On systems that are neither, their return values are unspecified.
425
426 =item int ecb_ctz32 (uint32_t x)
427
428 =item int ecb_ctz64 (uint64_t x)
429
430 Returns the index of the least significant bit set in C<x> (or
431 equivalently the number of bits set to 0 before the least significant bit
432 set), starting from 0. If C<x> is 0 the result is undefined.
433
434 For smaller types than C<uint32_t> you can safely use C<ecb_ctz32>.
435
436 For example:
437
438 ecb_ctz32 (3) = 0
439 ecb_ctz32 (6) = 1
440
441 =item bool ecb_is_pot32 (uint32_t x)
442
443 =item bool ecb_is_pot64 (uint32_t x)
444
445 Return true iff C<x> is a power of two or C<x == 0>.
446
447 For smaller types then C<uint32_t> you can safely use C<ecb_is_pot32>.
448
449 =item int ecb_ld32 (uint32_t x)
450
451 =item int ecb_ld64 (uint64_t x)
452
453 Returns the index of the most significant bit set in C<x>, or the number
454 of digits the number requires in binary (so that C<< 2**ld <= x <
455 2**(ld+1) >>). If C<x> is 0 the result is undefined. A common use case is
456 to compute the integer binary logarithm, i.e. C<floor (log2 (n))>, for
457 example to see how many bits a certain number requires to be encoded.
458
459 This function is similar to the "count leading zero bits" function, except
460 that that one returns how many zero bits are "in front" of the number (in
461 the given data type), while C<ecb_ld> returns how many bits the number
462 itself requires.
463
464 For smaller types than C<uint32_t> you can safely use C<ecb_ld32>.
465
466 =item int ecb_popcount32 (uint32_t x)
467
468 =item int ecb_popcount64 (uint64_t x)
469
470 Returns the number of bits set to 1 in C<x>.
471
472 For smaller types than C<uint32_t> you can safely use C<ecb_popcount32>.
473
474 For example:
475
476 ecb_popcount32 (7) = 3
477 ecb_popcount32 (255) = 8
478
479 =item uint8_t ecb_bitrev8 (uint8_t x)
480
481 =item uint16_t ecb_bitrev16 (uint16_t x)
482
483 =item uint32_t ecb_bitrev32 (uint32_t x)
484
485 Reverses the bits in x, i.e. the MSB becomes the LSB, MSB-1 becomes LSB+1
486 and so on.
487
488 Example:
489
490 ecb_bitrev8 (0xa7) = 0xea
491 ecb_bitrev32 (0xffcc4411) = 0x882233ff
492
493 =item uint32_t ecb_bswap16 (uint32_t x)
494
495 =item uint32_t ecb_bswap32 (uint32_t x)
496
497 =item uint64_t ecb_bswap64 (uint64_t x)
498
499 These functions return the value of the 16-bit (32-bit, 64-bit) value
500 C<x> after reversing the order of bytes (0x11223344 becomes 0x44332211 in
501 C<ecb_bswap32>).
502
503 =item uint8_t ecb_rotl8 (uint8_t x, unsigned int count)
504
505 =item uint16_t ecb_rotl16 (uint16_t x, unsigned int count)
506
507 =item uint32_t ecb_rotl32 (uint32_t x, unsigned int count)
508
509 =item uint64_t ecb_rotl64 (uint64_t x, unsigned int count)
510
511 =item uint8_t ecb_rotr8 (uint8_t x, unsigned int count)
512
513 =item uint16_t ecb_rotr16 (uint16_t x, unsigned int count)
514
515 =item uint32_t ecb_rotr32 (uint32_t x, unsigned int count)
516
517 =item uint64_t ecb_rotr64 (uint64_t x, unsigned int count)
518
519 These two families of functions return the value of C<x> after rotating
520 all the bits by C<count> positions to the right (C<ecb_rotr>) or left
521 (C<ecb_rotl>).
522
523 Current GCC versions understand these functions and usually compile them
524 to "optimal" code (e.g. a single C<rol> or a combination of C<shld> on
525 x86).
526
527 =back
528
529 =head2 ARITHMETIC
530
531 =over 4
532
533 =item x = ecb_mod (m, n)
534
535 Returns C<m> modulo C<n>, which is the same as the positive remainder
536 of the division operation between C<m> and C<n>, using floored
537 division. Unlike the C remainder operator C<%>, this function ensures that
538 the return value is always positive and that the two numbers I<m> and
539 I<m' = m + i * n> result in the same value modulo I<n> - in other words,
540 C<ecb_mod> implements the mathematical modulo operation, which is missing
541 in the language.
542
543 C<n> must be strictly positive (i.e. C<< >= 1 >>), while C<m> must be
544 negatable, that is, both C<m> and C<-m> must be representable in its
545 type (this typically excludes the minimum signed integer value, the same
546 limitation as for C</> and C<%> in C).
547
548 Current GCC versions compile this into an efficient branchless sequence on
549 almost all CPUs.
550
551 For example, when you want to rotate forward through the members of an
552 array for increasing C<m> (which might be negative), then you should use
553 C<ecb_mod>, as the C<%> operator might give either negative results, or
554 change direction for negative values:
555
556 for (m = -100; m <= 100; ++m)
557 int elem = myarray [ecb_mod (m, ecb_array_length (myarray))];
558
559 =item x = ecb_div_rd (val, div)
560
561 =item x = ecb_div_ru (val, div)
562
563 Returns C<val> divided by C<div> rounded down or up, respectively.
564 C<val> and C<div> must have integer types and C<div> must be strictly
565 positive. Note that these functions are implemented with macros in C
566 and with function templates in C++.
567
568 =back
569
570 =head2 UTILITY
571
572 =over 4
573
574 =item element_count = ecb_array_length (name)
575
576 Returns the number of elements in the array C<name>. For example:
577
578 int primes[] = { 2, 3, 5, 7, 11 };
579 int sum = 0;
580
581 for (i = 0; i < ecb_array_length (primes); i++)
582 sum += primes [i];
583
584 =back
585
586