[Linuxptp-devel] [PATCHv2 RFC 1/3] Add modular filter interface.

[Miroslav Lichvar]

Similarly to the servo interface, allow multiple filters to be
used for delay filtering. Convert mave to the new interface.

Signed-off-by: Miroslav Lichvar <***@redhat.com>
---
clock.c | 16 +++++++-------
filter.c | 46 +++++++++++++++++++++++++++++++++++++++++
filter.h | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
filter_private.h | 33 +++++++++++++++++++++++++++++
makefile | 2 +-
mave.c | 48 +++++++++++++++++++++++++-----------------
mave.h | 12 ++---------
port.c | 14 ++++++-------
8 files changed, 189 insertions(+), 45 deletions(-)
create mode 100644 filter.c
create mode 100644 filter.h
create mode 100644 filter_private.h

diff --git a/clock.c b/clock.c
index 819421e..ca3e521 100644
--- a/clock.c
+++ b/clock.c
@@ -26,7 +26,7 @@
#include "clock.h"
#include "clockadj.h"
#include "foreign.h"
-#include "mave.h"
+#include "filter.h"
#include "missing.h"
#include "msg.h"
#include "phc.h"
@@ -85,7 +85,7 @@ struct clock {
enum servo_state servo_state;
tmv_t master_offset;
tmv_t path_delay;
- struct mave *avg_delay;
+ struct filter *delay_filter;
struct freq_estimator fest;
struct time_status_np status;
double nrr;
@@ -119,7 +119,7 @@ void clock_destroy(struct clock *c)
phc_close(c->clkid);
}
servo_destroy(c->servo);
- mave_destroy(c->avg_delay);
+ filter_destroy(c->delay_filter);
stats_destroy(c->stats.offset);
stats_destroy(c->stats.freq);
stats_destroy(c->stats.delay);
@@ -630,9 +630,9 @@ struct clock *clock_create(int phc_index, struct interface *iface, int count,
return NULL;
}
c->servo_state = SERVO_UNLOCKED;
- c->avg_delay = mave_create(MAVE_LENGTH);
- if (!c->avg_delay) {
- pr_err("Failed to create moving average");
+ c->delay_filter = filter_create(FILTER_MOVING_AVERAGE, MAVE_LENGTH);
+ if (!c->delay_filter) {
+ pr_err("Failed to create delay filter");
return NULL;
}
c->stats_interval = dds->stats_interval;
@@ -983,7 +983,7 @@ void clock_path_delay(struct clock *c, struct timespec req, struct timestamp rx,
pr_warning("c3 %10lld", c3);
}

- c->path_delay = mave_accumulate(c->avg_delay, pd);
+ c->path_delay = filter_sample(c->delay_filter, pd);

c->cur.meanPathDelay = tmv_to_TimeInterval(c->path_delay);

@@ -1154,7 +1154,7 @@ static void handle_state_decision_event(struct clock *c)

if (!cid_eq(&best_id, &c->best_id)) {
clock_freq_est_reset(c);
- mave_reset(c->avg_delay);
+ filter_reset(c->delay_filter);
c->t1 = tmv_zero();
c->t2 = tmv_zero();
c->path_delay = 0;
diff --git a/filter.c b/filter.c
new file mode 100644
index 0000000..95c6bfc
--- /dev/null
+++ b/filter.c
@@ -0,0 +1,46 @@
+/**
+ * @file filter.c
+ * @note Copyright (C) 2013 Miroslav Lichvar <***@redhat.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include "filter_private.h"
+#include "mave.h"
+
+struct filter *filter_create(enum filter_type type, int length)
+{
+ switch (type) {
+ case FILTER_MOVING_AVERAGE:
+ return mave_create(length);
+ default:
+ return NULL;
+ }
+}
+
+void filter_destroy(struct filter *filter)
+{
+ filter->destroy(filter);
+}
+
+int64_t filter_sample(struct filter *filter, int64_t sample)
+{
+ return filter->sample(filter, sample);
+}
+
+void filter_reset(struct filter *filter)
+{
+ filter->reset(filter);
+}
diff --git a/filter.h b/filter.h
new file mode 100644
index 0000000..4d7b370
--- /dev/null
+++ b/filter.h
@@ -0,0 +1,63 @@
+/**
+ * @file filter.h
+ * @brief Implements a generic filter interface.
+ * @note Copyright (C) 2013 Miroslav Lichvar <***@redhat.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+#ifndef HAVE_FILTER_H
+#define HAVE_FILTER_H
+
+#include "tmv.h"
+
+/** Opaque type */
+struct filter;
+
+/**
+ * Defines the available filters.
+ */
+enum filter_type {
+ FILTER_MOVING_AVERAGE,
+};
+
+/**
+ * Create a new instance of a filter.
+ * @param type The type of the filter to create.
+ * @param length The filter's length.
+ * @return A pointer to a new filter on success, NULL otherwise.
+ */
+struct filter *filter_create(enum filter_type type, int length);
+
+/**
+ * Destroy an instance of a filter.
+ * @param filter Pointer to a filter obtained via @ref filter_create().
+ */
+void filter_destroy(struct filter *filter);
+
+/**
+ * Feed a sample into a filter.
+ * @param filter Pointer to a filter obtained via @ref filter_create().
+ * @param sample The input sample.
+ * @return The output value.
+ */
+tmv_t filter_sample(struct filter *filter, tmv_t sample);
+
+/**
+ * Reset a filter.
+ * @param filter Pointer to a filter obtained via @ref filter_create().
+ */
+void filter_reset(struct filter *filter);
+
+#endif
diff --git a/filter_private.h b/filter_private.h
new file mode 100644
index 0000000..26062b4
--- /dev/null
+++ b/filter_private.h
@@ -0,0 +1,33 @@
+/**
+ * @file filter_private.h
+ * @note Copyright (C) 2013 Miroslav Lichvar <***@redhat.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+#ifndef HAVE_FILTER_PRIVATE_H
+#define HAVE_FILTER_PRIVATE_H
+
+#include "tmv.h"
+#include "contain.h"
+
+struct filter {
+ void (*destroy)(struct filter *filter);
+
+ tmv_t (*sample)(struct filter *filter, tmv_t sample);
+
+ void (*reset)(struct filter *filter);
+};
+
+#endif
diff --git a/makefile b/makefile
index d79a1df..09e0782 100644
--- a/makefile
+++ b/makefile
@@ -32,7 +32,7 @@ VER = -DVER=$(version)
CFLAGS = -Wall $(VER) $(INC) $(DEBUG) $(FEAT_CFLAGS) $(EXTRA_CFLAGS)
LDLIBS = -lm -lrt $(EXTRA_LDFLAGS)
PRG = ptp4l pmc phc2sys hwstamp_ctl
-OBJ = bmc.o clock.o clockadj.o config.o fault.o fsm.o ptp4l.o mave.o \
+OBJ = bmc.o clock.o clockadj.o config.o fault.o filter.o fsm.o ptp4l.o mave.o \
msg.o phc.o pi.o port.o print.o raw.o servo.o sk.o stats.o tlv.o tmtab.o \
transport.o udp.o udp6.o uds.o util.o version.o

diff --git a/mave.c b/mave.c
index 7742f05..fd09e5a 100644
--- a/mave.c
+++ b/mave.c
@@ -20,8 +20,10 @@
#include <string.h>

#include "mave.h"
+#include "filter_private.h"

struct mave {
+ struct filter filter;
int cnt;
int len;
int index;
@@ -29,30 +31,17 @@ struct mave {
tmv_t *val;
};

-struct mave *mave_create(int length)
-{
- struct mave *m;
- m = calloc(1, sizeof(*m));
- if (!m) {
- return NULL;
- }
- m->val = calloc(1, length * sizeof(*m->val));
- if (!m->val) {
- free(m);
- return NULL;
- }
- m->len = length;
- return m;
-}
-
-void mave_destroy(struct mave *m)
+static void mave_destroy(struct filter *filter)
{
+ struct mave *m = container_of(filter, struct mave, filter);
free(m->val);
free(m);
}

-tmv_t mave_accumulate(struct mave *m, tmv_t val)
+static tmv_t mave_accumulate(struct filter *filter, tmv_t val)
{
+ struct mave *m = container_of(filter, struct mave, filter);
+
m->sum = tmv_sub(m->sum, m->val[m->index]);
m->val[m->index] = val;
m->index = (1 + m->index) % m->len;
@@ -63,10 +52,31 @@ tmv_t mave_accumulate(struct mave *m, tmv_t val)
return tmv_div(m->sum, m->cnt);
}

-void mave_reset(struct mave *m)
+static void mave_reset(struct filter *filter)
{
+ struct mave *m = container_of(filter, struct mave, filter);
+
m->cnt = 0;
m->index = 0;
m->sum = 0;
memset(m->val, 0, m->len * sizeof(*m->val));
}
+
+struct filter *mave_create(int length)
+{
+ struct mave *m;
+ m = calloc(1, sizeof(*m));
+ if (!m) {
+ return NULL;
+ }
+ m->filter.destroy = mave_destroy;
+ m->filter.sample = mave_accumulate;
+ m->filter.reset = mave_reset;
+ m->val = calloc(1, length * sizeof(*m->val));
+ if (!m->val) {
+ free(m);
+ return NULL;
+ }
+ m->len = length;
+ return &m->filter;
+}
diff --git a/mave.h b/mave.h
index 84241d4..8f170e4 100644
--- a/mave.h
+++ b/mave.h
@@ -20,16 +20,8 @@
#ifndef HAVE_MAVE_H
#define HAVE_MAVE_H

-#include "tmv.h"
+#include "filter.h"

-struct mave;
-
-struct mave *mave_create(int length);
-
-void mave_destroy(struct mave *m);
-
-tmv_t mave_accumulate(struct mave *m, tmv_t val);
-
-void mave_reset(struct mave *m);
+struct filter *mave_create(int length);

#endif
diff --git a/port.c b/port.c
index d98bb80..921f4c4 100644
--- a/port.c
+++ b/port.c
@@ -25,7 +25,7 @@

#include "bmc.h"
#include "clock.h"
-#include "mave.h"
+#include "filter.h"
#include "missing.h"
#include "msg.h"
#include "port.h"
@@ -82,7 +82,7 @@ struct port {
} seqnum;
struct tmtab tmtab;
tmv_t peer_delay;
- struct mave *avg_delay;
+ struct filter *delay_filter;
int log_sync_interval;
struct nrate_estimator nrate;
unsigned int pdr_missing;
@@ -1716,7 +1716,7 @@ calc:
pd = tmv_sub(pd, c2);
pd = tmv_div(pd, 2);

- p->peer_delay = mave_accumulate(p->avg_delay, pd);
+ p->peer_delay = filter_sample(p->delay_filter, pd);

p->peerMeanPathDelay = tmv_to_TimeInterval(p->peer_delay);

@@ -1845,7 +1845,7 @@ void port_close(struct port *p)
port_disable(p);
}
transport_destroy(p->trp);
- mave_destroy(p->avg_delay);
+ filter_destroy(p->delay_filter);
free(p);
}

@@ -2303,9 +2303,9 @@ struct port *port_open(int phc_index,
p->delayMechanism = interface->dm;
p->versionNumber = PTP_VERSION;

- p->avg_delay = mave_create(PORT_MAVE_LENGTH);
- if (!p->avg_delay) {
- pr_err("Failed to create moving average");
+ p->delay_filter = filter_create(FILTER_MOVING_AVERAGE, PORT_MAVE_LENGTH);
+ if (!p->delay_filter) {
+ pr_err("Failed to create delay filter");
transport_destroy(p->trp);
free(p);
return NULL;

[Miroslav Lichvar]

Add new options delay_filter and delay_filter_length to select the
filter and its length. They set both the clock delay filter and the port
peer delay filter. The default is now moving median with 10 samples.

Signed-off-by: Miroslav Lichvar <***@redhat.com>
---
clock.c | 3 ++-
config.c | 33 +++++++++++++++++++++++++++++++++
config.h | 3 +++
default.cfg | 2 ++
ds.h | 3 +++
gPTP.cfg | 2 ++
port.c | 3 ++-
ptp4l.8 | 9 +++++++++
ptp4l.c | 2 ++
9 files changed, 58 insertions(+), 2 deletions(-)

diff --git a/clock.c b/clock.c
index ca3e521..2a4f703 100644
--- a/clock.c
+++ b/clock.c
@@ -630,7 +630,8 @@ struct clock *clock_create(int phc_index, struct interface *iface, int count,
return NULL;
}
c->servo_state = SERVO_UNLOCKED;
- c->delay_filter = filter_create(FILTER_MOVING_AVERAGE, MAVE_LENGTH);
+ c->delay_filter = filter_create(dds->delay_filter,
+ dds->delay_filter_length);
if (!c->delay_filter) {
pr_err("Failed to create delay filter");
return NULL;
diff --git a/config.c b/config.c
index 7365bcc..6a6fa91 100644
--- a/config.c
+++ b/config.c
@@ -159,6 +159,7 @@ static enum parser_result parse_port_setting(const char *option,
int p)
{
enum parser_result r;
+ int val;

r = parse_pod_setting(option, value, &cfg->iface[p].pod);
if (r != NOT_PARSED)
@@ -183,6 +184,21 @@ static enum parser_result parse_port_setting(const char *option,
cfg->iface[p].dm = DM_P2P;
else
return BAD_VALUE;
+
+ } else if (!strcmp(option, "delay_filter")) {
+ if (!strcasecmp("MAVE", value))
+ cfg->iface[p].delay_filter = FILTER_MOVING_AVERAGE;
+ else if (!strcasecmp("MMED", value))
+ cfg->iface[p].delay_filter = FILTER_MOVING_MEDIAN;
+ else
+ return BAD_VALUE;
+
+ } else if (!strcmp(option, "delay_filter_length")) {
+ r = get_ranged_int(value, &val, 1, INT_MAX);
+ if (r != PARSED_OK)
+ return r;
+ cfg->iface[p].delay_filter_length = val;
+
} else
return NOT_PARSED;

@@ -505,6 +521,20 @@ static enum parser_result parse_global_setting(const char *option,
return r;
cfg->dds.time_source = val;

+ } else if (!strcmp(option, "delay_filter")) {
+ if (!strcasecmp("MAVE", value))
+ cfg->dds.delay_filter = FILTER_MOVING_AVERAGE;
+ else if (!strcasecmp("MMED", value))
+ cfg->dds.delay_filter = FILTER_MOVING_MEDIAN;
+ else
+ return BAD_VALUE;
+
+ } else if (!strcmp(option, "delay_filter_length")) {
+ r = get_ranged_int(value, &val, 1, INT_MAX);
+ if (r != PARSED_OK)
+ return r;
+ cfg->dds.delay_filter_length = val;
+
} else
return NOT_PARSED;

@@ -662,6 +692,9 @@ int config_create_interface(char *name, struct config *cfg)

sk_get_ts_info(name, &iface->ts_info);

+ iface->delay_filter = cfg->dds.delay_filter;
+ iface->delay_filter_length = cfg->dds.delay_filter_length;
+
cfg->nports++;

return i;
diff --git a/config.h b/config.h
index 9e0d6e6..7e540ad 100644
--- a/config.h
+++ b/config.h
@@ -22,6 +22,7 @@

#include "ds.h"
#include "dm.h"
+#include "filter.h"
#include "transport.h"
#include "servo.h"
#include "sk.h"
@@ -36,6 +37,8 @@ struct interface {
enum transport_type transport;
struct port_defaults pod;
struct sk_ts_info ts_info;
+ enum filter_type delay_filter;
+ int delay_filter_length;
};

#define CFG_IGNORE_DM (1 << 0)
diff --git a/default.cfg b/default.cfg
index 7ff66fb..72f7328 100644
--- a/default.cfg
+++ b/default.cfg
@@ -66,6 +66,8 @@ udp6_scope 0x0E
network_transport UDPv4
delay_mechanism E2E
time_stamping hardware
+delay_filter MMED
+delay_filter_length 10
#
# Clock description
#
diff --git a/ds.h b/ds.h
index 55ad043..242a580 100644
--- a/ds.h
+++ b/ds.h
@@ -22,6 +22,7 @@

#include "ddt.h"
#include "fault.h"
+#include "filter.h"

/* clock data sets */

@@ -56,6 +57,8 @@ struct default_ds {
int kernel_leap;
int time_source;
struct clock_description clock_desc;
+ enum filter_type delay_filter;
+ int delay_filter_length;
};

struct dataset {
diff --git a/gPTP.cfg b/gPTP.cfg
index a3ddd9d..fe43ef5 100644
--- a/gPTP.cfg
+++ b/gPTP.cfg
@@ -64,3 +64,5 @@ p2p_dst_mac 01:80:C2:00:00:0E
network_transport L2
delay_mechanism P2P
time_stamping hardware
+delay_filter MMED
+delay_filter_length 10
diff --git a/port.c b/port.c
index 921f4c4..509a428 100644
--- a/port.c
+++ b/port.c
@@ -2303,7 +2303,8 @@ struct port *port_open(int phc_index,
p->delayMechanism = interface->dm;
p->versionNumber = PTP_VERSION;

- p->delay_filter = filter_create(FILTER_MOVING_AVERAGE, PORT_MAVE_LENGTH);
+ p->delay_filter = filter_create(interface->delay_filter,
+ interface->delay_filter_length);
if (!p->delay_filter) {
pr_err("Failed to create delay filter");
transport_destroy(p->trp);
diff --git a/ptp4l.8 b/ptp4l.8
index c887b29..20a98f9 100644
--- a/ptp4l.8
+++ b/ptp4l.8
@@ -192,6 +192,15 @@ The default is UDPv4.
.B neighborPropDelayThresh
Upper limit for peer delay in nanoseconds. If the estimated peer delay is
greater than this value the port is marked as not 802.1AS capable.
+.TP
+.B delay_filter
+Select the algorithm used to filter the measured delay and peer delay. Possible
+values are MAVE for moving average and MMED for moving median.
+The default is MMED.
+.TP
+.B delay_filter_length
+The length of the delay filter in samples.
+The default is 10.

.SH PROGRAM AND CLOCK OPTIONS

diff --git a/ptp4l.c b/ptp4l.c
index fc14071..fac15c1 100644
--- a/ptp4l.c
+++ b/ptp4l.c
@@ -69,6 +69,8 @@ static struct config cfg_settings = {
.userDescription = { .max_symbols = 128 },
.manufacturerIdentity = { 0, 0, 0 },
},
+ .delay_filter = FILTER_MOVING_MEDIAN,
+ .delay_filter_length = 10,
},

.pod = {

[Richard Cochran]

Post by Miroslav Lichvar
@@ -183,6 +184,21 @@ static enum parser_result parse_port_setting(const char *option,
cfg->iface[p].dm = DM_P2P;
else
return BAD_VALUE;
+
+ } else if (!strcmp(option, "delay_filter")) {
+ if (!strcasecmp("MAVE", value))
+ cfg->iface[p].delay_filter = FILTER_MOVING_AVERAGE;
+ else if (!strcasecmp("MMED", value))
+ cfg->iface[p].delay_filter = FILTER_MOVING_MEDIAN;

I think for the configuration file, we might as well spell it out,
like "moving_average" and "moving_median". This makes the option
almost self-explanatory.

Thanks,
Richard

[Keller, Jacob E]

-----Original Message-----
Sent: Saturday, October 26, 2013 8:46 AM
To: Miroslav Lichvar
Subject: Re: [Linuxptp-devel] [PATCHv2 RFC 3/3] Add options to
configure delay filter.

Post by Miroslav Lichvar
@@ -183,6 +184,21 @@ static enum parser_result

parse_port_setting(const char *option,

Post by Miroslav Lichvar
cfg->iface[p].dm = DM_P2P;
else
return BAD_VALUE;
+
+ } else if (!strcmp(option, "delay_filter")) {
+ if (!strcasecmp("MAVE", value))
+ cfg->iface[p].delay_filter =

FILTER_MOVING_AVERAGE;

Post by Miroslav Lichvar
+ else if (!strcasecmp("MMED", value))
+ cfg->iface[p].delay_filter =

FILTER_MOVING_MEDIAN;
I think for the configuration file, we might as well spell it out,
like "moving_average" and "moving_median". This makes the option
almost self-explanatory.
Thanks,
Richard

I agree!

Regards,
Jake

[Miroslav Lichvar]

Median filter has an advantage over moving average that it is much less
sensitive to outliers.

For instance, it allows much faster recovery from an external clock
time step which happened between receiving sync message and sending
delay_req message. The measured delay includes a large error, but the
median is still a good estimate of the delay and the first step
correction applied by the servo is right.

In this implementation the median update has linear time complexity.

Signed-off-by: Miroslav Lichvar <***@redhat.com>
---
filter.c | 3 ++
filter.h | 1 +
makefile | 6 ++--
mmedian.c | 110 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
mmedian.h | 27 +++++++++++++++
5 files changed, 144 insertions(+), 3 deletions(-)
create mode 100644 mmedian.c
create mode 100644 mmedian.h

diff --git a/filter.c b/filter.c
index 95c6bfc..8a17dad 100644
--- a/filter.c
+++ b/filter.c
@@ -19,12 +19,15 @@

#include "filter_private.h"
#include "mave.h"
+#include "mmedian.h"

struct filter *filter_create(enum filter_type type, int length)
{
switch (type) {
case FILTER_MOVING_AVERAGE:
return mave_create(length);
+ case FILTER_MOVING_MEDIAN:
+ return mmedian_create(length);
default:
return NULL;
}
diff --git a/filter.h b/filter.h
index 4d7b370..5a196bc 100644
--- a/filter.h
+++ b/filter.h
@@ -30,6 +30,7 @@ struct filter;
*/
enum filter_type {
FILTER_MOVING_AVERAGE,
+ FILTER_MOVING_MEDIAN,
};

/**
diff --git a/makefile b/makefile
index 09e0782..6890f0e 100644
--- a/makefile
+++ b/makefile
@@ -32,9 +32,9 @@ VER = -DVER=$(version)
CFLAGS = -Wall $(VER) $(INC) $(DEBUG) $(FEAT_CFLAGS) $(EXTRA_CFLAGS)
LDLIBS = -lm -lrt $(EXTRA_LDFLAGS)
PRG = ptp4l pmc phc2sys hwstamp_ctl
-OBJ = bmc.o clock.o clockadj.o config.o fault.o filter.o fsm.o ptp4l.o mave.o \
- msg.o phc.o pi.o port.o print.o raw.o servo.o sk.o stats.o tlv.o tmtab.o \
- transport.o udp.o udp6.o uds.o util.o version.o
+OBJ = bmc.o clock.o clockadj.o config.o fault.o filter.o fsm.o ptp4l.o \
+ mave.o mmedian.o msg.o phc.o pi.o port.o print.o raw.o servo.o sk.o \
+ stats.o tlv.o tmtab.o transport.o udp.o udp6.o uds.o util.o version.o

OBJECTS = $(OBJ) hwstamp_ctl.o phc2sys.o pmc.o pmc_common.o sysoff.o
SRC = $(OBJECTS:.o=.c)
diff --git a/mmedian.c b/mmedian.c
new file mode 100644
index 0000000..9185cbb
--- /dev/null
+++ b/mmedian.c
@@ -0,0 +1,110 @@
+/**
+ * @file mmedian.c
+ * @note Copyright (C) 2013 Miroslav Lichvar <***@redhat.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+#include <stdlib.h>
+#include <string.h>
+
+#include "mmedian.h"
+#include "filter_private.h"
+
+struct mmedian {
+ struct filter filter;
+ int cnt;
+ int len;
+ int index;
+ /* Indices sorted by value. */
+ int *order;
+ /* Values stored in circular buffer. */
+ tmv_t *samples;
+};
+
+static void mmedian_destroy(struct filter *filter)
+{
+ struct mmedian *m = container_of(filter, struct mmedian, filter);
+ free(m->order);
+ free(m->samples);
+ free(m);
+}
+
+static tmv_t mmedian_sample(struct filter *filter, tmv_t sample)
+{
+ struct mmedian *m = container_of(filter, struct mmedian, filter);
+ int i;
+
+ m->samples[m->index] = sample;
+ if (m->cnt < m->len) {
+ m->cnt++;
+ } else {
+ /* Remove index of the replaced value from order. */
+ for (i = 0; i < m->cnt; i++)
+ if (m->order[i] == m->index)
+ break;
+ for (; i + 1 < m->cnt; i++)
+ m->order[i] = m->order[i + 1];
+ }
+
+ /* Insert index of the new value to order. */
+ for (i = m->cnt - 1; i > 0; i--) {
+ if (m->samples[m->order[i - 1]] <= m->samples[m->index])
+ break;
+ m->order[i] = m->order[i - 1];
+ }
+ m->order[i] = m->index;
+
+ m->index = (1 + m->index) % m->len;
+
+ if (m->cnt % 2)
+ return m->samples[m->order[m->cnt / 2]];
+ else
+ return tmv_div(tmv_add(m->samples[m->order[m->cnt / 2 - 1]],
+ m->samples[m->order[m->cnt / 2]]), 2);
+}
+
+static void mmedian_reset(struct filter *filter)
+{
+ struct mmedian *m = container_of(filter, struct mmedian, filter);
+ m->cnt = 0;
+ m->index = 0;
+}
+
+struct filter *mmedian_create(int length)
+{
+ struct mmedian *m;
+
+ if (length < 1)
+ return NULL;
+ m = calloc(1, sizeof(*m));
+ if (!m)
+ return NULL;
+ m->filter.destroy = mmedian_destroy;
+ m->filter.sample = mmedian_sample;
+ m->filter.reset = mmedian_reset;
+ m->order = calloc(1, length * sizeof(*m->order));
+ if (!m->order) {
+ free(m);
+ return NULL;
+ }
+ m->samples = calloc(1, length * sizeof(*m->samples));
+ if (!m->samples) {
+ free(m->order);
+ free(m);
+ return NULL;
+ }
+ m->len = length;
+ return &m->filter;
+}
diff --git a/mmedian.h b/mmedian.h
new file mode 100644
index 0000000..8fee0dc
--- /dev/null
+++ b/mmedian.h
@@ -0,0 +1,27 @@
+/**
+ * @file mmedian.h
+ * @brief Implements a moving median.
+ * @note Copyright (C) 2013 Miroslav Lichvar <***@redhat.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+#ifndef HAVE_MMEDIAN_H
+#define HAVE_MMEDIAN_H
+
+#include "filter.h"
+
+struct filter *mmedian_create(int length);
+
+#endif

[Richard Cochran]

Post by Miroslav Lichvar
+static tmv_t mmedian_sample(struct filter *filter, tmv_t sample)
+{
+ struct mmedian *m = container_of(filter, struct mmedian, filter);
+ int i;
+
+ m->samples[m->index] = sample;
+ if (m->cnt < m->len) {
+ m->cnt++;
+ } else {
+ /* Remove index of the replaced value from order. */
+ for (i = 0; i < m->cnt; i++)
+ if (m->order[i] == m->index)
+ break;
+ for (; i + 1 < m->cnt; i++)
+ m->order[i] = m->order[i + 1];
+ }
+
+ /* Insert index of the new value to order. */

Why not just use qsort(3)?

Thanks,
Richard

Post by Miroslav Lichvar
+ for (i = m->cnt - 1; i > 0; i--) {
+ if (m->samples[m->order[i - 1]] <= m->samples[m->index])
+ break;
+ m->order[i] = m->order[i - 1];
+ }
+ m->order[i] = m->index;
+
+ m->index = (1 + m->index) % m->len;
+
+ if (m->cnt % 2)
+ return m->samples[m->order[m->cnt / 2]];
+ else
+ return tmv_div(tmv_add(m->samples[m->order[m->cnt / 2 - 1]],
+ m->samples[m->order[m->cnt / 2]]), 2);
+}

[Richard Cochran]

Just getting around to looking at this, and I do like it. I have a few
minor comments.

In filter.c you have

Post by Miroslav Lichvar
+int64_t filter_sample(struct filter *filter, int64_t sample)

^^^^^^^

but in filter.h and elswehere

Post by Miroslav Lichvar
+tmv_t filter_sample(struct filter *filter, tmv_t sample);

^^^^^

Thanks,
Richard

[Miroslav Lichvar]

Post by Richard Cochran
Just getting around to looking at this, and I do like it. I have a few
minor comments.
In filter.c you have

Post by Miroslav Lichvar
+int64_t filter_sample(struct filter *filter, int64_t sample)

^^^^^^^
but in filter.h and elswehere

Post by Miroslav Lichvar
+tmv_t filter_sample(struct filter *filter, tmv_t sample);

^^^^^

I started the implementation with int64_t, but later changed it to
tmv_t and missed that place.

Post by Richard Cochran

Post by Miroslav Lichvar
+ /* Insert index of the new value to order. */

Why not just use qsort(3)?

It should be always faster than qsort() and it's just few lines of
code.

Post by Richard Cochran

Post by Miroslav Lichvar
+ } else if (!strcmp(option, "delay_filter")) {
+ if (!strcasecmp("MAVE", value))
+ cfg->iface[p].delay_filter = FILTER_MOVING_AVERAGE;
+ else if (!strcasecmp("MMED", value))
+ cfg->iface[p].delay_filter = FILTER_MOVING_MEDIAN;

I think for the configuration file, we might as well spell it out,
like "moving_average" and "moving_median". This makes the option
almost self-explanatory.

Ok, I'll change that. Thanks for the review.