Update SILK code using the CELT range coder
[opus.git] / src_SigProc_FIX / SKP_Silk_sort.c
similarity index 65%
rename from src/SKP_Silk_sort.c
rename to src_SigProc_FIX/SKP_Silk_sort.c
index 70930b5..add67a6 100644 (file)
@@ -29,7 +29,6 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 /* Best case:  O(n)   for an already sorted array            */\r
 /* Worst case: O(n^2) for an inversely sorted array          */\r
 /*                                                           */\r
-/* To be implemented:                                        */\r
 /* Shell short:    http://en.wikipedia.org/wiki/Shell_sort   */\r
 \r
 #include "SKP_Silk_SigProc_FIX.h"\r
@@ -65,7 +64,7 @@ void SKP_Silk_insertion_sort_increasing(
         index[ j + 1 ] = i;     /* Write index */\r
     }\r
 \r
-    /* If less than L values are asked check the remaining values,      */\r
+    /* If less than L values are asked for, check the remaining values, */\r
     /* but only spend CPU to ensure that the K first values are correct */\r
     for( i = K; i < L; i++ ) {\r
         value = a[ i ];\r
@@ -111,7 +110,7 @@ void SKP_Silk_insertion_sort_decreasing(
         index[ j + 1 ] = i;     /* Write index */\r
     }\r
 \r
-    /* If less than L values are asked check the remaining values,      */\r
+    /* If less than L values are asked for, check the remaining values, */\r
     /* but only spend CPU to ensure that the K first values are correct */\r
     for( i = K; i < L; i++ ) {\r
         value = a[ i ];\r
@@ -157,7 +156,7 @@ void SKP_Silk_insertion_sort_decreasing_int16(
         index[ j + 1 ] = i;     /* Write index */\r
     }\r
 \r
-    /* If less than L values are asked check the remaining values,        */\r
+    /* If less than L values are asked for, check the remaining values, */\r
     /* but only spend CPU to ensure that the K first values are correct */\r
     for( i = K; i < L; i++ ) {\r
         value = a[ i ];\r
@@ -193,3 +192,96 @@ void SKP_Silk_insertion_sort_increasing_all_values(
     }\r
 }\r
 \r
+void SKP_Silk_shell_insertion_sort_increasing(\r
+    SKP_int32           *a,             /* I/O:  Unsorted / Sorted vector               */\r
+    SKP_int             *index,         /* O:    Index vector for the sorted elements   */\r
+    const SKP_int       L,              /* I:    Vector length                          */\r
+    const SKP_int       K               /* I:    Number of correctly sorted positions   */\r
+)\r
+{\r
+    SKP_int32    value, inc_Q16_tmp;\r
+    SKP_int      i, j, inc, idx;\r
+   \r
+    /* Safety checks */\r
+    SKP_assert( K >  0 );\r
+    SKP_assert( L >  0 );\r
+    SKP_assert( L >= K );\r
+    \r
+    /* Calculate initial step size */\r
+    inc_Q16_tmp = SKP_LSHIFT( (SKP_int32)L, 15 );\r
+    inc = SKP_RSHIFT( inc_Q16_tmp, 16 );\r
+\r
+    /* Write start indices in index vector */\r
+    for( i = 0; i < K; i++ ) {\r
+        index[ i ] = i;\r
+    }\r
+\r
+    /* Shell sort first values */\r
+    while( inc > 0 ) {\r
+        for( i = inc; i < K; i++ ) {\r
+            value = a[ i ];\r
+            idx   = index[ i ];\r
+            for( j = i - inc; ( j >= 0 ) && ( value < a[ j ] ); j -= inc ) {\r
+                a[ j + inc ]     = a[ j ];     /* Shift value */\r
+                index[ j + inc ] = index[ j ]; /* Shift index */\r
+            }\r
+            a[ j + inc ]     = value; /* Write value */\r
+            index[ j + inc ] = idx;   /* Write index */\r
+        }\r
+        inc_Q16_tmp = SKP_SMULWB( inc_Q16_tmp, 29789 ); // 29789_Q16 = 2.2^(-1)_Q0\r
+        inc = SKP_RSHIFT_ROUND( inc_Q16_tmp, 16 );\r
+    }\r
+\r
+    /* If less than L values are asked for, check the remaining values, */\r
+    /* but only spend CPU to ensure that the K first values are correct */\r
+    /* Insertion sort remaining values */\r
+    for( i = K; i < L; i++ ) {\r
+        value = a[ i ];\r
+        if( value < a[ K - 1 ] ) {\r
+            for( j = K - 2; ( j >= 0 ) && ( value < a[ j ] ); j-- ) {\r
+                a[ j + 1 ]     = a[ j ];     /* Shift value */\r
+                index[ j + 1 ] = index[ j ]; /* Shift index */\r
+            }\r
+            a[ j + 1 ]     = value; /* Write value */\r
+            index[ j + 1 ] = i;     /* Write index */\r
+        }\r
+    }\r
+}\r
+\r
+void SKP_Silk_shell_sort_increasing_all_values(\r
+    SKP_int32           *a,             /* I/O:  Unsorted / Sorted vector               */\r
+    SKP_int             *index,         /* O:    Index vector for the sorted elements   */\r
+    const SKP_int       L               /* I:    Vector length                          */\r
+)\r
+{\r
+    SKP_int32    value, inc_Q16_tmp;\r
+    SKP_int      i, j, inc, idx;\r
+   \r
+    /* Safety checks */\r
+    SKP_assert( L >  0 );\r
\r
+    /* Calculate initial step size */\r
+    inc_Q16_tmp = SKP_LSHIFT( (SKP_int32)L, 15 );\r
+    inc = SKP_RSHIFT( inc_Q16_tmp, 16 );\r
+\r
+    /* Write start indices in index vector */\r
+    for( i = 0; i < L; i++ ) {\r
+        index[ i ] = i;\r
+    }\r
+\r
+    /* Sort vector elements by value, increasing order */\r
+    while( inc > 0 ) {\r
+        for( i = inc; i < L; i++ ) {\r
+            value = a[ i ];\r
+            idx = index[ i ];\r
+            for( j = i - inc; ( j >= 0 ) && ( value < a[ j ] ); j -= inc ) {\r
+                a[ j + inc ]     = a[ j ];     /* Shift value */\r
+                index[ j + inc ] = index[ j ]; /* Shift index */\r
+            }\r
+            a[ j + inc ] = value;   /* Write value */\r
+            index[ j + inc ] = idx; /* Write index */\r
+        }\r
+        inc_Q16_tmp = SKP_SMULWB( inc_Q16_tmp, 29789 ); // 29789_Q16 = 2.2^(-1)_Q0\r
+        inc = SKP_RSHIFT_ROUND( inc_Q16_tmp, 16 );\r
+    }\r
+}\r