texcompress_fxt1.c

mesa-6.5-minigui源码

         sx2 += t * t;
      }
      var = sx2 * teenth - sx * sx * teenth * teenth;
      if (maxvar < var) {
         maxvar = var;
         best = i;
      }
      if (variance) {
         variance[i] = var;
      }
   }

   return best;
}


static GLint
fxt1_choose (GLfloat vec[][MAX_COMP], GLint nv,
             GLubyte input[N_TEXELS][MAX_COMP], GLint nc, GLint n)
{
#if 0
   /* Choose colors from a grid.
    */
   GLint i, j;

   for (j = 0; j < nv; j++) {
      GLint m = j * (n - 1) / (nv - 1);
      for (i = 0; i < nc; i++) {
         vec[j][i] = input[m][i];
      }
   }
#else
   /* Our solution here is to find the darkest and brightest colors in
    * the 8x4 tile and use those as the two representative colors.
    * There are probably better algorithms to use (histogram-based).
    */
   GLint i, j, k;
   GLint minSum = 2000; /* big enough */
   GLint maxSum = -1; /* small enough */
   GLint minCol = 0; /* phoudoin: silent compiler! */
   GLint maxCol = 0; /* phoudoin: silent compiler! */

   struct {
      GLint flag;
      GLint key;
      GLint freq;
      GLint idx;
   } hist[N_TEXELS];
   GLint lenh = 0;

   _mesa_memset(hist, 0, sizeof(hist));

   for (k = 0; k < n; k++) {
      GLint l;
      GLint key = 0;
      GLint sum = 0;
      for (i = 0; i < nc; i++) {
         key <<= 8;
         key |= input[k][i];
         sum += input[k][i];
      }
      for (l = 0; l < n; l++) {
         if (!hist[l].flag) {
            /* alloc new slot */
            hist[l].flag = !0;
            hist[l].key = key;
            hist[l].freq = 1;
            hist[l].idx = k;
            lenh = l + 1;
            break;
         } else if (hist[l].key == key) {
            hist[l].freq++;
            break;
         }
      }
      if (minSum > sum) {
         minSum = sum;
         minCol = k;
      }
      if (maxSum < sum) {
         maxSum = sum;
         maxCol = k;
      }
   }

   if (lenh <= nv) {
      for (j = 0; j < lenh; j++) {
         for (i = 0; i < nc; i++) {
            vec[j][i] = (GLfloat)input[hist[j].idx][i];
         }
      }
      for (; j < nv; j++) {
         for (i = 0; i < nc; i++) {
            vec[j][i] = vec[0][i];
         }
      }
      return 0;
   }

   for (j = 0; j < nv; j++) {
      for (i = 0; i < nc; i++) {
         vec[j][i] = ((nv - 1 - j) * input[minCol][i] + j * input[maxCol][i] + (nv - 1) / 2) / (GLfloat)(nv - 1);
      }
   }
#endif

   return !0;
}


static GLint
fxt1_lloyd (GLfloat vec[][MAX_COMP], GLint nv,
            GLubyte input[N_TEXELS][MAX_COMP], GLint nc, GLint n)
{
   /* Use the generalized lloyd's algorithm for VQ:
    *     find 4 color vectors.
    *
    *     for each sample color
    *         sort to nearest vector.
    *
    *     replace each vector with the centroid of it's matching colors.
    *
    *     repeat until RMS doesn't improve.
    *
    *     if a color vector has no samples, or becomes the same as another
    *     vector, replace it with the color which is farthest from a sample.
    *
    * vec[][MAX_COMP]           initial vectors and resulting colors
    * nv                        number of resulting colors required
    * input[N_TEXELS][MAX_COMP] input texels
    * nc                        number of components in input / vec
    * n                         number of input samples
    */

   GLint sum[MAX_VECT][MAX_COMP]; /* used to accumulate closest texels */
   GLint cnt[MAX_VECT]; /* how many times a certain vector was chosen */
   GLfloat error, lasterror = 1e9;

   GLint i, j, k, rep;

   /* the quantizer */
   for (rep = 0; rep < LL_N_REP; rep++) {
      /* reset sums & counters */
      for (j = 0; j < nv; j++) {
         for (i = 0; i < nc; i++) {
            sum[j][i] = 0;
         }
         cnt[j] = 0;
      }
      error = 0;

      /* scan whole block */
      for (k = 0; k < n; k++) {
#if 1
         GLint best = -1;
         GLfloat err = 1e9; /* big enough */
         /* determine best vector */
         for (j = 0; j < nv; j++) {
            GLfloat e = (vec[j][0] - input[k][0]) * (vec[j][0] - input[k][0]) +
                      (vec[j][1] - input[k][1]) * (vec[j][1] - input[k][1]) +
                      (vec[j][2] - input[k][2]) * (vec[j][2] - input[k][2]);
            if (nc == 4) {
               e += (vec[j][3] - input[k][3]) * (vec[j][3] - input[k][3]);
            }
            if (e < err) {
               err = e;
               best = j;
            }
         }
#else
         GLint best = fxt1_bestcol(vec, nv, input[k], nc, &err);
#endif
         /* add in closest color */
         for (i = 0; i < nc; i++) {
            sum[best][i] += input[k][i];
         }
         /* mark this vector as used */
         cnt[best]++;
         /* accumulate error */
         error += err;
      }

      /* check RMS */
      if ((error < LL_RMS_E) ||
          ((error < lasterror) && ((lasterror - error) < LL_RMS_D))) {
         return !0; /* good match */
      }
      lasterror = error;

      /* move each vector to the barycenter of its closest colors */
      for (j = 0; j < nv; j++) {
         if (cnt[j]) {
            GLfloat div = 1.0F / cnt[j];
            for (i = 0; i < nc; i++) {
               vec[j][i] = div * sum[j][i];
            }
         } else {
            /* this vec has no samples or is identical with a previous vec */
            GLint worst = fxt1_worst(vec[j], input, nc, n);
            for (i = 0; i < nc; i++) {
               vec[j][i] = input[worst][i];
            }
         }
      }
   }

   return 0; /* could not converge fast enough */
}


static void
fxt1_quantize_CHROMA (GLuint *cc,
                      GLubyte input[N_TEXELS][MAX_COMP])
{
   const GLint n_vect = 4; /* 4 base vectors to find */
   const GLint n_comp = 3; /* 3 components: R, G, B */
   GLfloat vec[MAX_VECT][MAX_COMP];
   GLint i, j, k;
   Fx64 hi; /* high quadword */
   GLuint lohi, lolo; /* low quadword: hi dword, lo dword */

   if (fxt1_choose(vec, n_vect, input, n_comp, N_TEXELS) != 0) {
      fxt1_lloyd(vec, n_vect, input, n_comp, N_TEXELS);
   }

   FX64_MOV32(hi, 4); /* cc-chroma = "010" + unused bit */
   for (j = n_vect - 1; j >= 0; j--) {
      for (i = 0; i < n_comp; i++) {
         /* add in colors */
         FX64_SHL(hi, 5);
         FX64_OR32(hi, (GLuint)(vec[j][i] / 8.0F));
      }
   }
   ((Fx64 *)cc)[1] = hi;

   lohi = lolo = 0;
   /* right microtile */
   for (k = N_TEXELS - 1; k >= N_TEXELS/2; k--) {
      lohi <<= 2;
      lohi |= fxt1_bestcol(vec, n_vect, input[k], n_comp);
   }
   /* left microtile */
   for (; k >= 0; k--) {
      lolo <<= 2;
      lolo |= fxt1_bestcol(vec, n_vect, input[k], n_comp);
   }
   cc[1] = lohi;
   cc[0] = lolo;
}


static void
fxt1_quantize_ALPHA0 (GLuint *cc,
                      GLubyte input[N_TEXELS][MAX_COMP],
                      GLubyte reord[N_TEXELS][MAX_COMP], GLint n)
{
   const GLint n_vect = 3; /* 3 base vectors to find */
   const GLint n_comp = 4; /* 4 components: R, G, B, A */
   GLfloat vec[MAX_VECT][MAX_COMP];
   GLint i, j, k;
   Fx64 hi; /* high quadword */
   GLuint lohi, lolo; /* low quadword: hi dword, lo dword */

   /* the last vector indicates zero */
   for (i = 0; i < n_comp; i++) {
      vec[n_vect][i] = 0;
   }

   /* the first n texels in reord are guaranteed to be non-zero */
   if (fxt1_choose(vec, n_vect, reord, n_comp, n) != 0) {
      fxt1_lloyd(vec, n_vect, reord, n_comp, n);
   }

   FX64_MOV32(hi, 6); /* alpha = "011" + lerp = 0 */
   for (j = n_vect - 1; j >= 0; j--) {
      /* add in alphas */
      FX64_SHL(hi, 5);
      FX64_OR32(hi, (GLuint)(vec[j][ACOMP] / 8.0F));
   }
   for (j = n_vect - 1; j >= 0; j--) {
      for (i = 0; i < n_comp - 1; i++) {
         /* add in colors */
         FX64_SHL(hi, 5);
         FX64_OR32(hi, (GLuint)(vec[j][i] / 8.0F));
      }
   }
   ((Fx64 *)cc)[1] = hi;

   lohi = lolo = 0;
   /* right microtile */
   for (k = N_TEXELS - 1; k >= N_TEXELS/2; k--) {
      lohi <<= 2;
      lohi |= fxt1_bestcol(vec, n_vect + 1, input[k], n_comp);
   }
   /* left microtile */
   for (; k >= 0; k--) {
      lolo <<= 2;
      lolo |= fxt1_bestcol(vec, n_vect + 1, input[k], n_comp);
   }
   cc[1] = lohi;
   cc[0] = lolo;
}


static void
fxt1_quantize_ALPHA1 (GLuint *cc,
                      GLubyte input[N_TEXELS][MAX_COMP])
{
   const GLint n_vect = 3; /* highest vector number in each microtile */
   const GLint n_comp = 4; /* 4 components: R, G, B, A */
   GLfloat vec[1 + 1 + 1][MAX_COMP]; /* 1.5 extrema for each sub-block */
   GLfloat b, iv[MAX_COMP]; /* interpolation vector */
   GLint i, j, k;
   Fx64 hi; /* high quadword */
   GLuint lohi, lolo; /* low quadword: hi dword, lo dword */

   GLint minSum;
   GLint maxSum;
   GLint minColL = 0, maxColL = 0;
   GLint minColR = 0, maxColR = 0;
   GLint sumL = 0, sumR = 0;

   /* Our solution here is to find the darkest and brightest colors in
    * the 4x4 tile and use those as the two representative colors.
    * There are probably better algorithms to use (histogram-based).
    */
   minSum = 2000; /* big enough */
   maxSum = -1; /* small enough */
   for (k = 0; k < N_TEXELS / 2; k++) {
      GLint sum = 0;
      for (i = 0; i < n_comp; i++) {
         sum += input[k][i];
      }
      if (minSum > sum) {
         minSum = sum;
         minColL = k;
      }
      if (maxSum < sum) {
         maxSum = sum;
         maxColL = k;
      }
      sumL += sum;
   }
   minSum = 2000; /* big enough */
   maxSum = -1; /* small enough */
   for (; k < N_TEXELS; k++) {
      GLint sum = 0;
      for (i = 0; i < n_comp; i++) {
         sum += input[k][i];
      }
      if (minSum > sum) {
         minSum = sum;
         minColR = k;
      }
      if (maxSum < sum) {
         maxSum = sum;
         maxColR = k;
      }
      sumR += sum;
   }

   /* choose the common vector (yuck!) */
   {
      GLint j1, j2;
      GLint v1 = 0, v2 = 0;
      GLfloat err = 1e9; /* big enough */
      GLfloat tv[2 * 2][MAX_COMP]; /* 2 extrema for each sub-block */
      for (i = 0; i < n_comp; i++) {
         tv[0][i] = input[minColL][i];
         tv[1][i] = input[maxColL][i];
         tv[2][i] = input[minColR][i];
         tv[3][i] = input[maxColR][i];
      }
      for (j1 = 0; j1 < 2; j1++) {
         for (j2 = 2; j2 < 4; j2++) {
            GLfloat e = 0.0F;
            for (i = 0; i < n_comp; i++) {
               e += (tv[j1][i] - tv[j2][i]) * (tv[j1][i] - tv[j2][i]);
            }
            if (e < err) {
               err = e;
               v1 = j1;
               v2 = j2;
            }
         }
      }
      for (i = 0; i < n_comp; i++) {
         vec[0][i] = tv[1 - v1][i];
         vec[1][i] = (tv[v1][i] * sumL + tv[v2][i] * sumR) / (sumL + sumR);
         vec[2][i] = tv[5 - v2][i];
      }
   }

   /* left microtile */
   cc[0] = 0;
   if (minColL != maxColL) {
      /* compute interpolation vector */
      MAKEIVEC(n_vect, n_comp, iv, b, vec[0], vec[1]);

      /* add in texels */
      lolo = 0;
      for (k = N_TEXELS / 2 - 1; k >= 0; k--) {
         GLint texel;
         /* interpolate color */
         CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
         /* add in texel */
         lolo <<= 2;
         lolo |= texel;
      }
      
      cc[0] = lolo;
   }

   /* right microtile */
   cc[1] = 0;
   if (minColR != maxColR) {
      /* compute interpolation vector */
      MAKEIVEC(n_vect, n_comp, iv, b, vec[2], vec[1]);

      /* add in texels */
      lohi = 0;
      for (k = N_TEXELS - 1; k >= N_TEXELS / 2; k--) {
         GLint texel;
         /* interpolate color */
         CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
         /* add in texel */
         lohi <<= 2;
         lohi |= texel;