conv: Fix the traceback for tail biting codes

When picking the end state, looking only at the path metric
is highly suboptimal because in a tail biting code, we _know_ that
whatever treillis path is correct, it must start and end at the same
state. So we only consider path meeting that condition. We know any
path that doesn't isn't the right one. We only fallback to only
path metric if no path met that condition.

Fixes OS#4508

Signed-off-by: Sylvain Munaut <tnt@246tNt.com>
Change-Id: I87e51d3880c0fe7bf3d6cd08fd46517a424a230c

3 files changed, 89 insertions, 22 deletions

diff --git a/include/osmocom/core/conv.h b/include/osmocom/core/conv.h
index 1c14c3b0..84ef0f85 100644
--- a/include/osmocom/core/conv.h
+++ b/include/osmocom/core/conv.h
@@ -124,6 +124,7 @@ int osmo_conv_decode_scan(struct osmo_conv_decoder *decoder,
                           const sbit_t *input, int n);
 int osmo_conv_decode_flush(struct osmo_conv_decoder *decoder,
                            const sbit_t *input);
+int osmo_conv_decode_get_best_end_state(struct osmo_conv_decoder *decoder);
 int osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,
                                 ubit_t *output, int has_flush, int end_state);
 
diff --git a/src/conv.c b/src/conv.c
index 0e07e1f7..4696a44d 100644
--- a/src/conv.c
+++ b/src/conv.c
@@ -526,38 +526,87 @@ osmo_conv_decode_flush(struct osmo_conv_decoder *decoder,
 }
 
 int
-osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,
-                            ubit_t *output, int has_flush, int end_state)
+osmo_conv_decode_get_best_end_state(struct osmo_conv_decoder *decoder)
 {
 	const struct osmo_conv_code *code = decoder->code;
 
-	int min_ae;
-	uint8_t min_state, cur_state;
-	int i, s, n;
+	int min_ae, min_state;
+	int s;
 
-	uint8_t *sh_ptr;
+	/* If flushed, we _know_ the end state */
+	if (code->term == CONV_TERM_FLUSH)
+		return 0;
 
-	/* End state ? */
-	if (end_state < 0) {
-		/* Find state with least error */
-		min_ae = MAX_AE;
-		min_state = 0xff;
+	/* Search init */
+	min_state = -1;
+	min_ae = MAX_AE;
+
+	/* If tail biting, we search for the minimum path metric that
+	 * gives a circular traceback (i.e. start_state == end_state */
+	if (code->term == CONV_TERM_TAIL_BITING) {
+		int t, n, i;
+		uint8_t *sh_ptr;
 
 		for (s=0; s<decoder->n_states; s++)
 		{
+			/* Check if that state traces back to itself */
+			n = decoder->o_idx;
+			sh_ptr = &decoder->state_history[decoder->n_states * (n-1)];
+			t = s;
+
+			for (i=n-1; i>=0; i--) {
+				t = sh_ptr[t];
+				sh_ptr -= decoder->n_states;
+			}
+
+			if (s != t)
+				continue;
+
+			/* If it does, consider it */
 			if (decoder->ae[s] < min_ae) {
 				min_ae = decoder->ae[s];
 				min_state = s;
 			}
 		}
 
-		if (min_state == 0xff)
-			return -1;
-	} else {
-		min_state = (uint8_t) end_state;
-		min_ae = decoder->ae[end_state];
+		if (min_ae < MAX_AE)
+			return min_state;
 	}
 
+	/* Finally, just the lowest path metric */
+	for (s = 0; s < decoder->n_states; s++) {
+		/* Is it smaller ? */
+		if (decoder->ae[s] < min_ae) {
+			min_ae = decoder->ae[s];
+			min_state = s;
+		}
+	}
+
+	return min_state;
+}
+
+int
+osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,
+			    ubit_t *output, int has_flush, int end_state)
+{
+	const struct osmo_conv_code *code = decoder->code;
+
+	int min_ae;
+	uint8_t min_state, cur_state;
+	int i, n;
+
+	uint8_t *sh_ptr;
+
+	/* End state ? */
+	if (end_state < 0)
+		end_state = osmo_conv_decode_get_best_end_state(decoder);
+
+	if (end_state < 0)
+		return -1;
+
+	min_state = (uint8_t) end_state;
+	min_ae = decoder->ae[end_state];
+
 	/* Traceback */
 	cur_state = min_state;
 
@@ -598,8 +647,8 @@ osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,
  *
  * This is an all-in-one function, taking care of
  * \ref osmo_conv_decode_init, \ref osmo_conv_decode_scan,
- * \ref osmo_conv_decode_flush, \ref osmo_conv_decode_get_output and
- * \ref osmo_conv_decode_deinit.
+ * \ref osmo_conv_decode_flush, \ref osmo_conv_decode_get_best_end_state,
+ * \ref osmo_conv_decode_get_output and \ref osmo_conv_decode_deinit.
  */
 int
 osmo_conv_decode(const struct osmo_conv_code *code,
@@ -626,7 +675,7 @@ osmo_conv_decode(const struct osmo_conv_code *code,
 
 	rv = osmo_conv_decode_get_output(&decoder, output,
 		code->term == CONV_TERM_FLUSH,		/* has_flush */
-		code->term == CONV_TERM_FLUSH ? 0 : -1	/* end_state */
+		-1					/* end_state */
 	);
 
 	osmo_conv_decode_deinit(&decoder);
diff --git a/src/conv_acc.c b/src/conv_acc.c
index a26ed3b3..4bd3b076 100644
--- a/src/conv_acc.c
+++ b/src/conv_acc.c
@@ -483,10 +483,27 @@ static void _traceback_rec(struct vdecoder *dec,
  */
 static int traceback(struct vdecoder *dec, uint8_t *out, int term, int len)
 {
-	int i, sum, max = -1;
-	unsigned path, state = 0;
+	int i, j, sum, max = -1;
+	unsigned path, state = 0, state_scan;
 
-	if (term != CONV_TERM_FLUSH) {
+	if (term == CONV_TERM_TAIL_BITING) {
+		for (i = 0; i < dec->trellis.num_states; i++) {
+			state_scan = i;
+			for (j = len - 1; j >= 0; j--) {
+				path = dec->paths[j][state_scan] + 1;
+				state_scan = vstate_lshift(state_scan, dec->k, path);
+			}
+			if (state_scan != i)
+				continue;
+			sum = dec->trellis.sums[i];
+			if (sum > max) {
+				max = sum;
+				state = i;
+			}
+		}
+	}
+
+	if ((max < 0) && (term != CONV_TERM_FLUSH)) {
 		for (i = 0; i < dec->trellis.num_states; i++) {
 			sum = dec->trellis.sums[i];
 			if (sum > max) {