pvq: use small LUT for integer sqrt((n+3)/2) sqrt((n+2)/2)
authorTristan Matthews <tmatth@videolan.org>
Fri, 26 Aug 2016 04:00:40 +0000 (00:00 -0400)
committerTristan Matthews <tmatth@videolan.org>
Fri, 26 Aug 2016 16:18:51 +0000 (12:18 -0400)
objective1-fast:
PSNR YCbCr:     -0.11%      0.06%     -0.04%
   PSNRHVS:     -0.04%
      SSIM:     -0.05%
    MSSSIM:     -0.07%
 CIEDE2000:      0.03%

subset1:
PSNR YCbCr:     -0.11%      0.06%     -0.04%
   PSNRHVS:     -0.04%
      SSIM:     -0.05%
    MSSSIM:     -0.07%
 CIEDE2000:      0.03%

Makefile.am
src/pvq.c
tools/gen_sqrt_tbl.c [new file with mode: 0644]
tools/unix/Makefile

index a4b0203..bb29aa9 100644 (file)
@@ -209,6 +209,7 @@ tools_TARGETS = \
        tools/trans2d \
        tools/trans_gain \
        tools/gen_cdf \
+       tools/gen_sqrt_tbl \
        tools/compute_basis \
        tools/compute_haar_basis \
        tools/cos_search \
@@ -421,6 +422,11 @@ tools_gen_cdf_SOURCES = \
 tools_gen_cdf_CFLAGS = $(OGG_CFLAGS) $(PNG_CFLAGS)
 tools_gen_cdf_LDADD = $(OGG_LIBS) $(PNG_LIBS) $(LIBM)
 
+# gen_sqrt_tbl
+tools_gen_sqrt_tbl_SOURCES = \
+       tools/gen_sqrt_tbl.c
+tools_gen_sqrt_tbl_LDADD = $(LIBM)
+
 # compute_basis
 tools_compute_basis_SOURCES = \
        tools/compute_basis.c \
index 98d0d69..1337d87 100644 (file)
--- a/src/pvq.c
+++ b/src/pvq.c
@@ -859,6 +859,8 @@ od_val32 od_pvq_compute_theta(int t, int max_theta) {
   else return 0;
 }
 
+#define OD_SQRT_TBL_SHIFT (10)
+
 #define OD_ITHETA_SHIFT 15
 /** Compute the number of pulses used for PVQ encoding a vector from
  * available metrics (encode and decode side)
@@ -875,6 +877,14 @@ od_val32 od_pvq_compute_theta(int t, int max_theta) {
  */
 int od_pvq_compute_k(od_val32 qcg, int itheta, od_val32 theta, int noref, int n,
  od_val16 beta, int nodesync) {
+#if !defined(OD_FLOAT_PVQ)
+  /*Lookup table for sqrt(n+3/2) and sqrt(n+2/2) in Q10.
+    Real max values are 32792 and 32784, but clamped to stay within 16 bits.
+    Update with tools/gen_sqrt_tbl if needed.*/
+  static const od_val16 od_sqrt_table[2][13] = {
+   {0, 0, 0, 0, 2290, 2985, 4222, 0, 8256, 0, 16416, 0, 32767},
+   {0, 0, 0, 0, 2401, 3072, 4284, 0, 8287, 0, 16432, 0, 32767}};
+#endif
   if (noref) {
     if (qcg == 0) return 0;
     if (n == 15 && qcg == OD_CGAIN_SCALE && beta > OD_BETA(1.25)) {
@@ -886,13 +896,13 @@ int od_pvq_compute_k(od_val32 qcg, int itheta, od_val32 theta, int noref, int n,
        sqrt((n + 3)/2)/beta));
 #else
       od_val16 rt;
-      int sqrt_shift;
-      rt = od_sqrt((n + 3) >> 1, &sqrt_shift);
+      OD_ASSERT(OD_ILOG(n + 1) < 13);
+      rt = od_sqrt_table[1][OD_ILOG(n + 1)];
       /*FIXME: get rid of 64-bit mul.*/
       return OD_MAXI(1, OD_SHR_ROUND((int64_t)((qcg
        - (int64_t)OD_QCONST32(.2, OD_CGAIN_SHIFT))*
        OD_MULT16_16_QBETA(od_beta_rcp(beta), rt)), OD_CGAIN_SHIFT
-       + sqrt_shift));
+       + OD_SQRT_TBL_SHIFT));
 #endif
     }
   }
@@ -908,13 +918,13 @@ int od_pvq_compute_k(od_val32 qcg, int itheta, od_val32 theta, int noref, int n,
 #if defined(OD_FLOAT_PVQ)
       return OD_MAXI(1, (int)floor(.5 + (itheta - .2)*sqrt((n + 2)/2)));
 #else
-      od_val32 rt;
-      int sqrt_outshift;
-      rt = od_sqrt((n + 2)/2, &sqrt_outshift);
+      od_val16 rt;
+      OD_ASSERT(OD_ILOG(n + 1) < 13);
+      rt = od_sqrt_table[0][OD_ILOG(n + 1)];
       /*FIXME: get rid of 64-bit mul.*/
       return OD_MAXI(1, OD_VSHR_ROUND(((OD_SHL(itheta, OD_ITHETA_SHIFT)
        - OD_QCONST32(.2, OD_ITHETA_SHIFT)))*(int64_t)rt,
-       sqrt_outshift + OD_ITHETA_SHIFT));
+       OD_SQRT_TBL_SHIFT + OD_ITHETA_SHIFT));
 #endif
     }
     else {
diff --git a/tools/gen_sqrt_tbl.c b/tools/gen_sqrt_tbl.c
new file mode 100644 (file)
index 0000000..c4fe366
--- /dev/null
@@ -0,0 +1,35 @@
+#include <stdio.h>
+#include <stdint.h>
+#include <math.h>
+#include "../src/odintrin.h"
+#define OD_SQRT_TBL_SHIFT (10)
+
+int main()
+{
+  int i;
+  static int n[13] = {0, 0, 0, 0, 8, 15, 32, 0, 128, 0, 512, 0, 2048};
+  printf("static const od_val16 table[2][13] = {\n");
+  printf("{");
+  for (i = 0; i < 13; i++) {
+    if (n[i]) {
+      printf("%d, ", OD_MINI(32767, (int32_t)floor(.5
+       + (1 << OD_SQRT_TBL_SHIFT)*sqrt((n[i] + 2)/2.))));
+    }
+    else {
+      printf("0, ");
+    }
+  }
+  printf("},\n");
+  printf("{");
+  for (i = 0; i < 13; i++) {
+    if (n[i]) {
+      printf("%d, ", OD_MINI(32767, (int32_t)floor(.5
+       + (1 << OD_SQRT_TBL_SHIFT)*sqrt((n[i] + 3)/2.))));
+    }
+    else {
+      printf("0, ");
+    }
+  }
+  printf("}};\n");
+  return 0;
+}
index 724004a..abd31a0 100644 (file)
@@ -319,6 +319,20 @@ GEN_CDF_CSOURCES:=${GEN_CDF_LOCAL_CSOURCES:%=${LOCALSRCDIR}/%} \
  ${GEN_CDF_LIB_CSOURCES:%=${LIBSRCDIR}/%}
 GEN_CDF_TARGET:=gen_cdf
 
+#gen_sqrt_tbl
+GEN_SQRT_TBL_LOCAL_CSOURCES = \
+gen_sqrt_tbl.c
+
+GEN_SQRT_TBL_LIB_CSOURCES =
+
+GEN_SQRT_TBL_LDFLAGS = -lm
+
+GEN_SQRT_TBL_OBJS:=${GEN_SQRT_TBL_LOCAL_CSOURCES} ${GEN_SQRT_TBL_LIB_CSOURCES}
+GEN_SQRT_TBL_OBJS:=${GEN_SQRT_TBL_OBJS:%.c=${WORKDIR}/%.o}
+GEN_SQRT_TBL_CSOURCES:=${GEN_SQRT_TBL_LOCAL_CSOURCES:%=${LOCALSRCDIR}/%} \
+ ${GEN_SQRT_TBL_LIB_CSOURCES:%=${LIBSRCDIR}/%}
+GEN_SQRT_TBL_TARGET:=gen_sqrt_tbl
+
 #gen_laplace_tables
 GEN_LAPLACE_TABLES_LOCAL_CSOURCES = \
 gen_laplace_tables.c