ewma.hh

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

#ifndef CLICK_EWMA_HH
#define CLICK_EWMA_HH
#include <click/glue.hh>
#include <click/confparse.hh>
CLICK_DECLS

/** @file <click/ewma.hh>
 *  @brief  Click's classes for supporting exponentially weighted moving
 *  averages.
 */

/** @class DirectEWMAX include/click/ewma.hh <click/ewma.hh>
 *  @brief  An exponentially weighted moving average.
 *
 *  The DirectEWMAX template class represents a simple exponentially weighted
 *  moving average.  The average starts out with value 0.  The update()
 *  function adds a new observation to the average.
 *
 *  The template parameter P defines three EWMA parameters: value type,
 *  stability shift, and scale factor.
 *
 *  The value type is simply the unsigned integral type used to store the
 *  average.  It is also the type of each observation.  <code>unsigned</code>
 *  and <code>uint64_t</code> are examples.
 *
 *  The stability shift specifies alpha, the stability parameter.  Concretely,
 *  alpha = 1. / (2 ** stability_shift).  Thus, a stability shift of 4
 *  corresponds to an alpha of 1/16.
 *
 *  The scaling factor specifies how many bits of fraction are kept per
 *  observation.  Fraction bits are necessary to account for small differences
 *  between observations.  For example, consider a EWMA with value 0, alpha
 *  1/16, and 0 bits of fraction.  Assume the EWMA begins to observe a stream
 *  of observations equal to 1.  Despite these observations, the EWMA's value
 *  will never change from 0, since the 1/16 alpha factor rounds the new
 *  observations down to 0.  At least 4 bits of fraction are required to
 *  account for this difference.  There is a tradeoff: the more bits of
 *  fraction, the more precise the EWMA, but the less bits available to
 *  account for large values.
 *
 *  These EWMA parameters are defined by five of P's members, two typedefs and
 *  three possibly static member functions.
 *
 *  <dl>
 *  <dt><strong>P::value_type</strong></dt>
 *  <dd>The EWMA's value type.  Example: <code>unsigned</code>.</dd>
 *
 *  <dt><strong>P::signed_value_type</strong></dt>
 *  <dd>The signed version of <code>P::value_type</code>.  Used internally.
 *  Example: <code>int</code>.</dd>
 *
 *  <dt><strong>unsigned P::stability_shift()</strong></dt>
 *  <dd>This function should return this EWMA's stability shift
 *  (see above).</dd>
 *
 *  <dt><strong>unsigned P::scale()</strong></dt>
 *  <dd>This function should return this EWMA's scaling factor
 *  (see above).</dd>
 *
 *  <dt><strong>unsigned P::compensation()</strong></dt>
 *  <dd>This function should return this EWMA's stability compensation,
 *  which normally equals 1 @<@< (stability_shift - 1).</dd>
 *  </dl>
 *
 *  Since DirectEWMAX inherits from an object of type P, these members are
 *  also directly available to callers.
 *
 *  The FixedEWMAXParameters and StabilityEWMAXParameters types are good
 *  template arguments for DirectEWMAX.
 *
 *  @sa RateEWMAX
 */
template <typename P>
class DirectEWMAX : public P { public:

    typedef typename P::value_type value_type;

    /** @brief Construct a EWMA with initial average 0. */
    DirectEWMAX()
	: _avg(0) {
    }

    /** @brief Construct a EWMA with initial scaled average @a scaled_value. */
    DirectEWMAX(value_type scaled_value)
	: _avg(scaled_value) {
    }

    /** @brief Return the current scaled moving average.
     *  @note The returned value has scale() bits of fraction. */
    value_type scaled_average() const {
	return _avg;
    }

    /** @brief Return the current moving average, rounded up.
     *  @note The returned value is unscaled (has zero bits of fraction). */
    value_type unscaled_average() const {
	return (_avg + (P::scaled_one() >> 1)) >> P::scale();
    }

    /** @brief Reset the EWMA to value 0. */
    void clear() {
	_avg = 0;
    }

    /** @brief  Assign the EWMA to scaled average @a scaled_value. */
    inline void assign(value_type scaled_value) {
	_avg = scaled_value;
    }

    /** @brief  Update the moving average with a new observation.
     *  @param  x  the observation (unscaled) */
    inline void update(value_type x);

    /** @brief  Update the moving average with @a n identical observations.
     *  @param  x  the observation (unscaled)
     *  @param  n  number of observations
     *  @note   This may be faster than calling update(@a x) @a n
     *  times. */
    void update_n(value_type x, unsigned n);

    /** @brief  Unparse the current average into a String.
     *  @note   The returned value is unscaled, but may contain a fractional
     *  part. */
    String unparse() const;

    /** @brief  Update the moving average with a new observation (deprecated).
     *  @param  x  the observation (unscaled)
     *  @deprecated  Use update() instead. */
    inline void update_with(value_type x) CLICK_DEPRECATED;

  private:

    value_type _avg;

};

template <typename P>
inline void
DirectEWMAX<P>::update(value_type x)
{
    value_type x_scaled = (x << P::scale()) + P::compensation();
    unsigned stability = P::stability_shift();
#if HAVE_ARITHMETIC_RIGHT_SHIFT
    _avg += static_cast<typename P::signed_value_type>(x_scaled - _avg) >> stability;
#else
    if (x_scaled < _avg)
	_avg -= (_avg - x_scaled) >> stability;
    else
	_avg += (x_scaled - _avg) >> stability;
#endif
}

template <typename P>
void
DirectEWMAX<P>::update_n(value_type x, unsigned n)
{
    // XXX use table lookup
    value_type x_scaled = x << P::scale();
    if (n >= 100)
	_avg = x_scaled;
    else {
	x_scaled += P::compensation();
	unsigned stability = P::stability_shift();
#if HAVE_ARITHMETIC_RIGHT_SHIFT
	for (; n > 0; n--)
	    _avg += static_cast<typename P::signed_value_type>(x_scaled - _avg) >> stability;
#else
	if (x_scaled < _avg)
	    for (; n > 0; n--)
		_avg -= (_avg - x_scaled) >> stability;
	else
	    for (; n > 0; n--)
		_avg += (x_scaled - _avg) >> stability;
#endif
    }
}

template <typename P>
inline String
DirectEWMAX<P>::unparse() const
{
    return cp_unparse_real2(scaled_average(), P::scale());
}

template <typename P>
inline void
DirectEWMAX<P>::update_with(value_type x)
{
    update(x);
}

/** @class FixedEWMAXParameters include/click/ewma.hh <click/ewma.hh>
 *  @brief  Parameters for a EWMA with constant scaling factor and stability
 *  shift.
 *
 *  The FixedEWMAXParameters template class is used as a template argument to
 *  DirectEWMAX.  It defines a EWMA with fixed constant scaling factor and
 *  stability shift.  FixedEWMAXParameters's first template argument is the
 *  EWMA's stability shift, its second template argument is the EWMA's scaling
 *  factor, its third template argument is the EWMA's value type, and the
 *  fourth template argument is the EWMA's signed value type.
 *
 *  Example 1: <code>DirectEWMAX@<FixedEWMAXParameters@<4, 10, unsigned, int@>
 *  @></code> defines a EWMA with alpha 1/16 (stability shift 4), scaling
 *  factor 10, and value type unsigned.  (These are the default parameters
 *  available in the DirectEWMA typedef.)
 *
 *  Example 2: <code>DirectEWMAX@<FixedEWMAXParameters@<3, 10, uint64_t,
 *  int64_t@> @></code> defines a EWMA with alpha 1/8 (stability shift 3),
 *  scaling factor 10, and value type uint64_t.
 */
template <unsigned STABILITY, unsigned SCALE, typename T = unsigned, typename U = int>
class FixedEWMAXParameters { public:

    typedef T value_type;
    typedef U signed_value_type;

    /** @brief  Return this EWMA's stability shift.
     *  @return  the 1st template parameter */
    static unsigned stability_shift() {
	return STABILITY;
    }

    /** @brief  Return this EWMA's scaling factor (bits of fraction).
     *  @return  the 2nd template parameter */
    static unsigned scale() {
	static_assert(SCALE < sizeof(T) * 8);
	return SCALE;
    }

    /** @brief  Return this EWMA's scaled value for one. */
    static value_type scaled_one() {
	return (value_type) 1 << SCALE;
    }

    /** @brief  Return this EWMA's compensation.
     *  @return  1 << (stability_shift() - 1) */
    static unsigned compensation() {
	return 1 << (STABILITY - 1);
    }

};

/** @brief A DirectEWMAX with stability shift 4 (alpha 1/16), scaling factor
 *  10 (10 bits of fraction), and underlying type <code>unsigned</code>. */
typedef DirectEWMAX<FixedEWMAXParameters<4, 10> > DirectEWMA;

/** @brief A DirectEWMAX with stability shift 3 (alpha 1/8), scaling factor
 *  10 (10 bits of fraction), and underlying type <code>unsigned</code>. */
typedef DirectEWMAX<FixedEWMAXParameters<3, 10> > FastDirectEWMA;


/** @class StabilityEWMAXParameters include/click/ewma.hh <click/ewma.hh>
 *  @brief  Parameters for a EWMA with constant scaling factor
 *	    and user-settable alpha.
 *
 *  The StabilityEWMAXParameters template class is used as a template argument
 *  to DirectEWMAX.  It defines a EWMA with fixed constant scaling factor.
 *  StabilityEWMAXParameters's first template argument is the EWMA's scaling
 *  factor, its second template argument is the EWMA's value type, and the
 *  third template argument is the EWMA's signed value type.