XZ decompressor: Fix decoding of empty LZMA2 streams
[linux-2.6.git] / lib / average.c
1 /*
2  * lib/average.c
3  *
4  * This source code is licensed under the GNU General Public License,
5  * Version 2.  See the file COPYING for more details.
6  */
7
8 #include <linux/module.h>
9 #include <linux/average.h>
10 #include <linux/bug.h>
11 #include <linux/log2.h>
12
13 /**
14  * DOC: Exponentially Weighted Moving Average (EWMA)
15  *
16  * These are generic functions for calculating Exponentially Weighted Moving
17  * Averages (EWMA). We keep a structure with the EWMA parameters and a scaled
18  * up internal representation of the average value to prevent rounding errors.
19  * The factor for scaling up and the exponential weight (or decay rate) have to
20  * be specified thru the init fuction. The structure should not be accessed
21  * directly but only thru the helper functions.
22  */
23
24 /**
25  * ewma_init() - Initialize EWMA parameters
26  * @avg: Average structure
27  * @factor: Factor to use for the scaled up internal value. The maximum value
28  *      of averages can be ULONG_MAX/(factor*weight). For performance reasons
29  *      factor has to be a power of 2.
30  * @weight: Exponential weight, or decay rate. This defines how fast the
31  *      influence of older values decreases. For performance reasons weight has
32  *      to be a power of 2.
33  *
34  * Initialize the EWMA parameters for a given struct ewma @avg.
35  */
36 void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
37 {
38         WARN_ON(!is_power_of_2(weight) || !is_power_of_2(factor));
39
40         avg->weight = ilog2(weight);
41         avg->factor = ilog2(factor);
42         avg->internal = 0;
43 }
44 EXPORT_SYMBOL(ewma_init);
45
46 /**
47  * ewma_add() - Exponentially weighted moving average (EWMA)
48  * @avg: Average structure
49  * @val: Current value
50  *
51  * Add a sample to the average.
52  */
53 struct ewma *ewma_add(struct ewma *avg, unsigned long val)
54 {
55         avg->internal = avg->internal  ?
56                 (((avg->internal << avg->weight) - avg->internal) +
57                         (val << avg->factor)) >> avg->weight :
58                 (val << avg->factor);
59         return avg;
60 }
61 EXPORT_SYMBOL(ewma_add);