From 419b2be813e3391e046858b7e3d5f07a81f3d263 Mon Sep 17 00:00:00 2001
From: Vitor Sessak <vitor1001@gmail.com>
Date: Sun, 22 Nov 2009 22:25:58 +0000
Subject: [PATCH] Make sorting function used in TwinVQ a shared function

Originally committed as revision 20584 to svn://svn.ffmpeg.org/ffmpeg/trunk
---
 libavcodec/lsp.c    |  9 +++++++++
 libavcodec/lsp.h    |  7 +++++++
 libavcodec/twinvq.c | 13 +------------
 3 files changed, 17 insertions(+), 12 deletions(-)

diff --git a/libavcodec/lsp.c b/libavcodec/lsp.c
index ce0fbc28b..739e1e0bf 100644
--- a/libavcodec/lsp.c
+++ b/libavcodec/lsp.c
@@ -173,3 +173,12 @@ void ff_acelp_lspd2lpc(const double *lsp, float *lpc, int lp_half_order)
         lpc2[-lp_half_order] = 0.5*(paf-qaf);
     }
 }
+
+void ff_sort_nearly_sorted_floats(float *vals, int len)
+{
+    int i,j;
+
+    for (i = 0; i < len - 1; i++)
+        for (j = i; j >= 0 && vals[j] > vals[j+1]; j--)
+            FFSWAP(float, vals[j], vals[j+1]);
+}
diff --git a/libavcodec/lsp.h b/libavcodec/lsp.h
index 9c02000aa..5a9d47b0e 100644
--- a/libavcodec/lsp.h
+++ b/libavcodec/lsp.h
@@ -97,4 +97,11 @@ void ff_acelp_lp_decode(int16_t* lp_1st, int16_t* lp_2nd, const int16_t* lsp_2nd
  */
 void ff_acelp_lspd2lpc(const double *lsp, float *lpc, int lp_half_order);
 
+/**
+ * Sort values in ascending order.
+ *
+ * @note O(n) if data already sorted, O(n^2) - otherwise
+ */
+void ff_sort_nearly_sorted_floats(float *vals, int len);
+
 #endif /* AVCODEC_LSP_H */
diff --git a/libavcodec/twinvq.c b/libavcodec/twinvq.c
index 814a0b081..8e198ea10 100644
--- a/libavcodec/twinvq.c
+++ b/libavcodec/twinvq.c
@@ -536,17 +536,6 @@ static void rearrange_lsp(int order, float *lsp, float min_dist)
         }
 }
 
-static void bubblesort(float *lsp, int lp_order)
-{
-    int i,j;
-
-    /* sort lsp in ascending order. float bubble agorithm,
-       O(n) if data already sorted, O(n^2) - otherwise */
-    for (i = 0; i < lp_order - 1; i++)
-        for (j = i; j >= 0 && lsp[j] > lsp[j+1]; j--)
-            FFSWAP(float, lsp[j], lsp[j+1]);
-}
-
 static void decode_lsp(TwinContext *tctx, int lpc_idx1, uint8_t *lpc_idx2,
                        int lpc_hist_idx, float *lsp, float *hist)
 {
@@ -583,7 +572,7 @@ static void decode_lsp(TwinContext *tctx, int lpc_idx1, uint8_t *lpc_idx2,
 
     rearrange_lsp(mtab->n_lsp, lsp, 0.0001);
     rearrange_lsp(mtab->n_lsp, lsp, 0.000095);
-    bubblesort(lsp, mtab->n_lsp);
+    ff_sort_nearly_sorted_floats(lsp, mtab->n_lsp);
 }
 
 static void dec_lpc_spectrum_inv(TwinContext *tctx, float *lsp,
-- 
2.11.0