Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Mesa 3-D graphics library
  3.  * Version:  7.1
  4.  *
  5.  * Copyright (C) 1999-2008  Brian Paul   All Rights Reserved.
  6.  *
  7.  * Permission is hereby granted, free of charge, to any person obtaining a
  8.  * copy of this software and associated documentation files (the "Software"),
  9.  * to deal in the Software without restriction, including without limitation
  10.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  11.  * and/or sell copies of the Software, and to permit persons to whom the
  12.  * Software is furnished to do so, subject to the following conditions:
  13.  *
  14.  * The above copyright notice and this permission notice shall be included
  15.  * in all copies or substantial portions of the Software.
  16.  *
  17.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  18.  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  20.  * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  21.  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  22.  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23.  */
  24.  
  25.  
  26. /**
  27.  * \file texcompress_fxt1.c
  28.  * GL_3DFX_texture_compression_FXT1 support.
  29.  */
  30.  
  31.  
  32. #include "glheader.h"
  33. #include "imports.h"
  34. #include "colormac.h"
  35. #include "image.h"
  36. #include "macros.h"
  37. #include "mipmap.h"
  38. #include "texcompress.h"
  39. #include "texcompress_fxt1.h"
  40. #include "texstore.h"
  41.  
  42.  
  43. #if FEATURE_texture_fxt1
  44.  
  45.  
  46. static void
  47. fxt1_encode (GLuint width, GLuint height, GLint comps,
  48.              const void *source, GLint srcRowStride,
  49.              void *dest, GLint destRowStride);
  50.  
  51. void
  52. fxt1_decode_1 (const void *texture, GLint stride,
  53.                GLint i, GLint j, GLchan *rgba);
  54.  
  55.  
  56. /**
  57.  * Store user's image in rgb_fxt1 format.
  58.  */
  59. GLboolean
  60. _mesa_texstore_rgb_fxt1(TEXSTORE_PARAMS)
  61. {
  62.    const GLchan *pixels;
  63.    GLint srcRowStride;
  64.    GLubyte *dst;
  65.    const GLint texWidth = dstRowStride * 8 / 16; /* a bit of a hack */
  66.    const GLchan *tempImage = NULL;
  67.  
  68.    ASSERT(dstFormat == MESA_FORMAT_RGB_FXT1);
  69.    ASSERT(dstXoffset % 8 == 0);
  70.    ASSERT(dstYoffset % 4 == 0);
  71.    ASSERT(dstZoffset     == 0);
  72.    (void) dstZoffset;
  73.    (void) dstImageOffsets;
  74.  
  75.    if (srcFormat != GL_RGB ||
  76.        srcType != CHAN_TYPE ||
  77.        ctx->_ImageTransferState ||
  78.        srcPacking->SwapBytes) {
  79.       /* convert image to RGB/GLchan */
  80.       tempImage = _mesa_make_temp_chan_image(ctx, dims,
  81.                                              baseInternalFormat,
  82.                                              _mesa_get_format_base_format(dstFormat),
  83.                                              srcWidth, srcHeight, srcDepth,
  84.                                              srcFormat, srcType, srcAddr,
  85.                                              srcPacking);
  86.       if (!tempImage)
  87.          return GL_FALSE; /* out of memory */
  88.       pixels = tempImage;
  89.       srcRowStride = 3 * srcWidth;
  90.       srcFormat = GL_RGB;
  91.    }
  92.    else {
  93.       pixels = (const GLchan *) srcAddr;
  94.       srcRowStride = _mesa_image_row_stride(srcPacking, srcWidth, srcFormat,
  95.                                             srcType) / sizeof(GLchan);
  96.    }
  97.  
  98.    dst = _mesa_compressed_image_address(dstXoffset, dstYoffset, 0,
  99.                                         dstFormat,
  100.                                         texWidth, (GLubyte *) dstAddr);
  101.  
  102.    fxt1_encode(srcWidth, srcHeight, 3, pixels, srcRowStride,
  103.                dst, dstRowStride);
  104.  
  105.    if (tempImage)
  106.       free((void*) tempImage);
  107.  
  108.    return GL_TRUE;
  109. }
  110.  
  111.  
  112. /**
  113.  * Store user's image in rgba_fxt1 format.
  114.  */
  115. GLboolean
  116. _mesa_texstore_rgba_fxt1(TEXSTORE_PARAMS)
  117. {
  118.    const GLchan *pixels;
  119.    GLint srcRowStride;
  120.    GLubyte *dst;
  121.    GLint texWidth = dstRowStride * 8 / 16; /* a bit of a hack */
  122.    const GLchan *tempImage = NULL;
  123.  
  124.    ASSERT(dstFormat == MESA_FORMAT_RGBA_FXT1);
  125.    ASSERT(dstXoffset % 8 == 0);
  126.    ASSERT(dstYoffset % 4 == 0);
  127.    ASSERT(dstZoffset     == 0);
  128.    (void) dstZoffset;
  129.    (void) dstImageOffsets;
  130.  
  131.    if (srcFormat != GL_RGBA ||
  132.        srcType != CHAN_TYPE ||
  133.        ctx->_ImageTransferState ||
  134.        srcPacking->SwapBytes) {
  135.       /* convert image to RGBA/GLchan */
  136.       tempImage = _mesa_make_temp_chan_image(ctx, dims,
  137.                                              baseInternalFormat,
  138.                                              _mesa_get_format_base_format(dstFormat),
  139.                                              srcWidth, srcHeight, srcDepth,
  140.                                              srcFormat, srcType, srcAddr,
  141.                                              srcPacking);
  142.       if (!tempImage)
  143.          return GL_FALSE; /* out of memory */
  144.       pixels = tempImage;
  145.       srcRowStride = 4 * srcWidth;
  146.       srcFormat = GL_RGBA;
  147.    }
  148.    else {
  149.       pixels = (const GLchan *) srcAddr;
  150.       srcRowStride = _mesa_image_row_stride(srcPacking, srcWidth, srcFormat,
  151.                                             srcType) / sizeof(GLchan);
  152.    }
  153.  
  154.    dst = _mesa_compressed_image_address(dstXoffset, dstYoffset, 0,
  155.                                         dstFormat,
  156.                                         texWidth, (GLubyte *) dstAddr);
  157.  
  158.    fxt1_encode(srcWidth, srcHeight, 4, pixels, srcRowStride,
  159.                dst, dstRowStride);
  160.  
  161.    if (tempImage)
  162.       free((void*) tempImage);
  163.  
  164.    return GL_TRUE;
  165. }
  166.  
  167.  
  168. void
  169. _mesa_fetch_texel_2d_f_rgba_fxt1( const struct gl_texture_image *texImage,
  170.                                   GLint i, GLint j, GLint k, GLfloat *texel )
  171. {
  172.    /* just sample as GLchan and convert to float here */
  173.    GLchan rgba[4];
  174.    (void) k;
  175.    fxt1_decode_1(texImage->Data, texImage->RowStride, i, j, rgba);
  176.    texel[RCOMP] = CHAN_TO_FLOAT(rgba[RCOMP]);
  177.    texel[GCOMP] = CHAN_TO_FLOAT(rgba[GCOMP]);
  178.    texel[BCOMP] = CHAN_TO_FLOAT(rgba[BCOMP]);
  179.    texel[ACOMP] = CHAN_TO_FLOAT(rgba[ACOMP]);
  180. }
  181.  
  182.  
  183. void
  184. _mesa_fetch_texel_2d_f_rgb_fxt1( const struct gl_texture_image *texImage,
  185.                                  GLint i, GLint j, GLint k, GLfloat *texel )
  186. {
  187.    /* just sample as GLchan and convert to float here */
  188.    GLchan rgba[4];
  189.    (void) k;
  190.    fxt1_decode_1(texImage->Data, texImage->RowStride, i, j, rgba);
  191.    texel[RCOMP] = CHAN_TO_FLOAT(rgba[RCOMP]);
  192.    texel[GCOMP] = CHAN_TO_FLOAT(rgba[GCOMP]);
  193.    texel[BCOMP] = CHAN_TO_FLOAT(rgba[BCOMP]);
  194.    texel[ACOMP] = 1.0F;
  195. }
  196.  
  197.  
  198.  
  199. /***************************************************************************\
  200.  * FXT1 encoder
  201.  *
  202.  * The encoder was built by reversing the decoder,
  203.  * and is vaguely based on Texus2 by 3dfx. Note that this code
  204.  * is merely a proof of concept, since it is highly UNoptimized;
  205.  * moreover, it is sub-optimal due to initial conditions passed
  206.  * to Lloyd's algorithm (the interpolation modes are even worse).
  207. \***************************************************************************/
  208.  
  209.  
  210. #define MAX_COMP 4 /* ever needed maximum number of components in texel */
  211. #define MAX_VECT 4 /* ever needed maximum number of base vectors to find */
  212. #define N_TEXELS 32 /* number of texels in a block (always 32) */
  213. #define LL_N_REP 50 /* number of iterations in lloyd's vq */
  214. #define LL_RMS_D 10 /* fault tolerance (maximum delta) */
  215. #define LL_RMS_E 255 /* fault tolerance (maximum error) */
  216. #define ALPHA_TS 2 /* alpha threshold: (255 - ALPHA_TS) deemed opaque */
  217. #define ISTBLACK(v) (*((GLuint *)(v)) == 0)
  218.  
  219.  
  220. /*
  221.  * Define a 64-bit unsigned integer type and macros
  222.  */
  223. #if 1
  224.  
  225. #define FX64_NATIVE 1
  226.  
  227. typedef uint64_t Fx64;
  228.  
  229. #define FX64_MOV32(a, b) a = b
  230. #define FX64_OR32(a, b)  a |= b
  231. #define FX64_SHL(a, c)   a <<= c
  232.  
  233. #else
  234.  
  235. #define FX64_NATIVE 0
  236.  
  237. typedef struct {
  238.    GLuint lo, hi;
  239. } Fx64;
  240.  
  241. #define FX64_MOV32(a, b) a.lo = b
  242. #define FX64_OR32(a, b)  a.lo |= b
  243.  
  244. #define FX64_SHL(a, c)                                 \
  245.    do {                                                \
  246.        if ((c) >= 32) {                                \
  247.           a.hi = a.lo << ((c) - 32);                   \
  248.           a.lo = 0;                                    \
  249.        } else {                                        \
  250.           a.hi = (a.hi << (c)) | (a.lo >> (32 - (c))); \
  251.           a.lo <<= (c);                                \
  252.        }                                               \
  253.    } while (0)
  254.  
  255. #endif
  256.  
  257.  
  258. #define F(i) (GLfloat)1 /* can be used to obtain an oblong metric: 0.30 / 0.59 / 0.11 */
  259. #define SAFECDOT 1 /* for paranoids */
  260.  
  261. #define MAKEIVEC(NV, NC, IV, B, V0, V1)  \
  262.    do {                                  \
  263.       /* compute interpolation vector */ \
  264.       GLfloat d2 = 0.0F;                 \
  265.       GLfloat rd2;                       \
  266.                                          \
  267.       for (i = 0; i < NC; i++) {         \
  268.          IV[i] = (V1[i] - V0[i]) * F(i); \
  269.          d2 += IV[i] * IV[i];            \
  270.       }                                  \
  271.       rd2 = (GLfloat)NV / d2;            \
  272.       B = 0;                             \
  273.       for (i = 0; i < NC; i++) {         \
  274.          IV[i] *= F(i);                  \
  275.          B -= IV[i] * V0[i];             \
  276.          IV[i] *= rd2;                   \
  277.       }                                  \
  278.       B = B * rd2 + 0.5f;                \
  279.    } while (0)
  280.  
  281. #define CALCCDOT(TEXEL, NV, NC, IV, B, V)\
  282.    do {                                  \
  283.       GLfloat dot = 0.0F;                \
  284.       for (i = 0; i < NC; i++) {         \
  285.          dot += V[i] * IV[i];            \
  286.       }                                  \
  287.       TEXEL = (GLint)(dot + B);          \
  288.       if (SAFECDOT) {                    \
  289.          if (TEXEL < 0) {                \
  290.             TEXEL = 0;                   \
  291.          } else if (TEXEL > NV) {        \
  292.             TEXEL = NV;                  \
  293.          }                               \
  294.       }                                  \
  295.    } while (0)
  296.  
  297.  
  298. static GLint
  299. fxt1_bestcol (GLfloat vec[][MAX_COMP], GLint nv,
  300.               GLubyte input[MAX_COMP], GLint nc)
  301. {
  302.    GLint i, j, best = -1;
  303.    GLfloat err = 1e9; /* big enough */
  304.  
  305.    for (j = 0; j < nv; j++) {
  306.       GLfloat e = 0.0F;
  307.       for (i = 0; i < nc; i++) {
  308.          e += (vec[j][i] - input[i]) * (vec[j][i] - input[i]);
  309.       }
  310.       if (e < err) {
  311.          err = e;
  312.          best = j;
  313.       }
  314.    }
  315.  
  316.    return best;
  317. }
  318.  
  319.  
  320. static GLint
  321. fxt1_worst (GLfloat vec[MAX_COMP],
  322.             GLubyte input[N_TEXELS][MAX_COMP], GLint nc, GLint n)
  323. {
  324.    GLint i, k, worst = -1;
  325.    GLfloat err = -1.0F; /* small enough */
  326.  
  327.    for (k = 0; k < n; k++) {
  328.       GLfloat e = 0.0F;
  329.       for (i = 0; i < nc; i++) {
  330.          e += (vec[i] - input[k][i]) * (vec[i] - input[k][i]);
  331.       }
  332.       if (e > err) {
  333.          err = e;
  334.          worst = k;
  335.       }
  336.    }
  337.  
  338.    return worst;
  339. }
  340.  
  341.  
  342. static GLint
  343. fxt1_variance (GLdouble variance[MAX_COMP],
  344.                GLubyte input[N_TEXELS][MAX_COMP], GLint nc, GLint n)
  345. {
  346.    GLint i, k, best = 0;
  347.    GLint sx, sx2;
  348.    GLdouble var, maxvar = -1; /* small enough */
  349.    GLdouble teenth = 1.0 / n;
  350.  
  351.    for (i = 0; i < nc; i++) {
  352.       sx = sx2 = 0;
  353.       for (k = 0; k < n; k++) {
  354.          GLint t = input[k][i];
  355.          sx += t;
  356.          sx2 += t * t;
  357.       }
  358.       var = sx2 * teenth - sx * sx * teenth * teenth;
  359.       if (maxvar < var) {
  360.          maxvar = var;
  361.          best = i;
  362.       }
  363.       if (variance) {
  364.          variance[i] = var;
  365.       }
  366.    }
  367.  
  368.    return best;
  369. }
  370.  
  371.  
  372. static GLint
  373. fxt1_choose (GLfloat vec[][MAX_COMP], GLint nv,
  374.              GLubyte input[N_TEXELS][MAX_COMP], GLint nc, GLint n)
  375. {
  376. #if 0
  377.    /* Choose colors from a grid.
  378.     */
  379.    GLint i, j;
  380.  
  381.    for (j = 0; j < nv; j++) {
  382.       GLint m = j * (n - 1) / (nv - 1);
  383.       for (i = 0; i < nc; i++) {
  384.          vec[j][i] = input[m][i];
  385.       }
  386.    }
  387. #else
  388.    /* Our solution here is to find the darkest and brightest colors in
  389.     * the 8x4 tile and use those as the two representative colors.
  390.     * There are probably better algorithms to use (histogram-based).
  391.     */
  392.    GLint i, j, k;
  393.    GLint minSum = 2000; /* big enough */
  394.    GLint maxSum = -1; /* small enough */
  395.    GLint minCol = 0; /* phoudoin: silent compiler! */
  396.    GLint maxCol = 0; /* phoudoin: silent compiler! */
  397.  
  398.    struct {
  399.       GLint flag;
  400.       GLint key;
  401.       GLint freq;
  402.       GLint idx;
  403.    } hist[N_TEXELS];
  404.    GLint lenh = 0;
  405.  
  406.    memset(hist, 0, sizeof(hist));
  407.  
  408.    for (k = 0; k < n; k++) {
  409.       GLint l;
  410.       GLint key = 0;
  411.       GLint sum = 0;
  412.       for (i = 0; i < nc; i++) {
  413.          key <<= 8;
  414.          key |= input[k][i];
  415.          sum += input[k][i];
  416.       }
  417.       for (l = 0; l < n; l++) {
  418.          if (!hist[l].flag) {
  419.             /* alloc new slot */
  420.             hist[l].flag = !0;
  421.             hist[l].key = key;
  422.             hist[l].freq = 1;
  423.             hist[l].idx = k;
  424.             lenh = l + 1;
  425.             break;
  426.          } else if (hist[l].key == key) {
  427.             hist[l].freq++;
  428.             break;
  429.          }
  430.       }
  431.       if (minSum > sum) {
  432.          minSum = sum;
  433.          minCol = k;
  434.       }
  435.       if (maxSum < sum) {
  436.          maxSum = sum;
  437.          maxCol = k;
  438.       }
  439.    }
  440.  
  441.    if (lenh <= nv) {
  442.       for (j = 0; j < lenh; j++) {
  443.          for (i = 0; i < nc; i++) {
  444.             vec[j][i] = (GLfloat)input[hist[j].idx][i];
  445.          }
  446.       }
  447.       for (; j < nv; j++) {
  448.          for (i = 0; i < nc; i++) {
  449.             vec[j][i] = vec[0][i];
  450.          }
  451.       }
  452.       return 0;
  453.    }
  454.  
  455.    for (j = 0; j < nv; j++) {
  456.       for (i = 0; i < nc; i++) {
  457.          vec[j][i] = ((nv - 1 - j) * input[minCol][i] + j * input[maxCol][i] + (nv - 1) / 2) / (GLfloat)(nv - 1);
  458.       }
  459.    }
  460. #endif
  461.  
  462.    return !0;
  463. }
  464.  
  465.  
  466. static GLint
  467. fxt1_lloyd (GLfloat vec[][MAX_COMP], GLint nv,
  468.             GLubyte input[N_TEXELS][MAX_COMP], GLint nc, GLint n)
  469. {
  470.    /* Use the generalized lloyd's algorithm for VQ:
  471.     *     find 4 color vectors.
  472.     *
  473.     *     for each sample color
  474.     *         sort to nearest vector.
  475.     *
  476.     *     replace each vector with the centroid of its matching colors.
  477.     *
  478.     *     repeat until RMS doesn't improve.
  479.     *
  480.     *     if a color vector has no samples, or becomes the same as another
  481.     *     vector, replace it with the color which is farthest from a sample.
  482.     *
  483.     * vec[][MAX_COMP]           initial vectors and resulting colors
  484.     * nv                        number of resulting colors required
  485.     * input[N_TEXELS][MAX_COMP] input texels
  486.     * nc                        number of components in input / vec
  487.     * n                         number of input samples
  488.     */
  489.  
  490.    GLint sum[MAX_VECT][MAX_COMP]; /* used to accumulate closest texels */
  491.    GLint cnt[MAX_VECT]; /* how many times a certain vector was chosen */
  492.    GLfloat error, lasterror = 1e9;
  493.  
  494.    GLint i, j, k, rep;
  495.  
  496.    /* the quantizer */
  497.    for (rep = 0; rep < LL_N_REP; rep++) {
  498.       /* reset sums & counters */
  499.       for (j = 0; j < nv; j++) {
  500.          for (i = 0; i < nc; i++) {
  501.             sum[j][i] = 0;
  502.          }
  503.          cnt[j] = 0;
  504.       }
  505.       error = 0;
  506.  
  507.       /* scan whole block */
  508.       for (k = 0; k < n; k++) {
  509. #if 1
  510.          GLint best = -1;
  511.          GLfloat err = 1e9; /* big enough */
  512.          /* determine best vector */
  513.          for (j = 0; j < nv; j++) {
  514.             GLfloat e = (vec[j][0] - input[k][0]) * (vec[j][0] - input[k][0]) +
  515.                       (vec[j][1] - input[k][1]) * (vec[j][1] - input[k][1]) +
  516.                       (vec[j][2] - input[k][2]) * (vec[j][2] - input[k][2]);
  517.             if (nc == 4) {
  518.                e += (vec[j][3] - input[k][3]) * (vec[j][3] - input[k][3]);
  519.             }
  520.             if (e < err) {
  521.                err = e;
  522.                best = j;
  523.             }
  524.          }
  525. #else
  526.          GLint best = fxt1_bestcol(vec, nv, input[k], nc, &err);
  527. #endif
  528.          assert(best >= 0);
  529.          /* add in closest color */
  530.          for (i = 0; i < nc; i++) {
  531.             sum[best][i] += input[k][i];
  532.          }
  533.          /* mark this vector as used */
  534.          cnt[best]++;
  535.          /* accumulate error */
  536.          error += err;
  537.       }
  538.  
  539.       /* check RMS */
  540.       if ((error < LL_RMS_E) ||
  541.           ((error < lasterror) && ((lasterror - error) < LL_RMS_D))) {
  542.          return !0; /* good match */
  543.       }
  544.       lasterror = error;
  545.  
  546.       /* move each vector to the barycenter of its closest colors */
  547.       for (j = 0; j < nv; j++) {
  548.          if (cnt[j]) {
  549.             GLfloat div = 1.0F / cnt[j];
  550.             for (i = 0; i < nc; i++) {
  551.                vec[j][i] = div * sum[j][i];
  552.             }
  553.          } else {
  554.             /* this vec has no samples or is identical with a previous vec */
  555.             GLint worst = fxt1_worst(vec[j], input, nc, n);
  556.             for (i = 0; i < nc; i++) {
  557.                vec[j][i] = input[worst][i];
  558.             }
  559.          }
  560.       }
  561.    }
  562.  
  563.    return 0; /* could not converge fast enough */
  564. }
  565.  
  566.  
  567. static void
  568. fxt1_quantize_CHROMA (GLuint *cc,
  569.                       GLubyte input[N_TEXELS][MAX_COMP])
  570. {
  571.    const GLint n_vect = 4; /* 4 base vectors to find */
  572.    const GLint n_comp = 3; /* 3 components: R, G, B */
  573.    GLfloat vec[MAX_VECT][MAX_COMP];
  574.    GLint i, j, k;
  575.    Fx64 hi; /* high quadword */
  576.    GLuint lohi, lolo; /* low quadword: hi dword, lo dword */
  577.  
  578.    if (fxt1_choose(vec, n_vect, input, n_comp, N_TEXELS) != 0) {
  579.       fxt1_lloyd(vec, n_vect, input, n_comp, N_TEXELS);
  580.    }
  581.  
  582.    FX64_MOV32(hi, 4); /* cc-chroma = "010" + unused bit */
  583.    for (j = n_vect - 1; j >= 0; j--) {
  584.       for (i = 0; i < n_comp; i++) {
  585.          /* add in colors */
  586.          FX64_SHL(hi, 5);
  587.          FX64_OR32(hi, (GLuint)(vec[j][i] / 8.0F));
  588.       }
  589.    }
  590.    ((Fx64 *)cc)[1] = hi;
  591.  
  592.    lohi = lolo = 0;
  593.    /* right microtile */
  594.    for (k = N_TEXELS - 1; k >= N_TEXELS/2; k--) {
  595.       lohi <<= 2;
  596.       lohi |= fxt1_bestcol(vec, n_vect, input[k], n_comp);
  597.    }
  598.    /* left microtile */
  599.    for (; k >= 0; k--) {
  600.       lolo <<= 2;
  601.       lolo |= fxt1_bestcol(vec, n_vect, input[k], n_comp);
  602.    }
  603.    cc[1] = lohi;
  604.    cc[0] = lolo;
  605. }
  606.  
  607.  
  608. static void
  609. fxt1_quantize_ALPHA0 (GLuint *cc,
  610.                       GLubyte input[N_TEXELS][MAX_COMP],
  611.                       GLubyte reord[N_TEXELS][MAX_COMP], GLint n)
  612. {
  613.    const GLint n_vect = 3; /* 3 base vectors to find */
  614.    const GLint n_comp = 4; /* 4 components: R, G, B, A */
  615.    GLfloat vec[MAX_VECT][MAX_COMP];
  616.    GLint i, j, k;
  617.    Fx64 hi; /* high quadword */
  618.    GLuint lohi, lolo; /* low quadword: hi dword, lo dword */
  619.  
  620.    /* the last vector indicates zero */
  621.    for (i = 0; i < n_comp; i++) {
  622.       vec[n_vect][i] = 0;
  623.    }
  624.  
  625.    /* the first n texels in reord are guaranteed to be non-zero */
  626.    if (fxt1_choose(vec, n_vect, reord, n_comp, n) != 0) {
  627.       fxt1_lloyd(vec, n_vect, reord, n_comp, n);
  628.    }
  629.  
  630.    FX64_MOV32(hi, 6); /* alpha = "011" + lerp = 0 */
  631.    for (j = n_vect - 1; j >= 0; j--) {
  632.       /* add in alphas */
  633.       FX64_SHL(hi, 5);
  634.       FX64_OR32(hi, (GLuint)(vec[j][ACOMP] / 8.0F));
  635.    }
  636.    for (j = n_vect - 1; j >= 0; j--) {
  637.       for (i = 0; i < n_comp - 1; i++) {
  638.          /* add in colors */
  639.          FX64_SHL(hi, 5);
  640.          FX64_OR32(hi, (GLuint)(vec[j][i] / 8.0F));
  641.       }
  642.    }
  643.    ((Fx64 *)cc)[1] = hi;
  644.  
  645.    lohi = lolo = 0;
  646.    /* right microtile */
  647.    for (k = N_TEXELS - 1; k >= N_TEXELS/2; k--) {
  648.       lohi <<= 2;
  649.       lohi |= fxt1_bestcol(vec, n_vect + 1, input[k], n_comp);
  650.    }
  651.    /* left microtile */
  652.    for (; k >= 0; k--) {
  653.       lolo <<= 2;
  654.       lolo |= fxt1_bestcol(vec, n_vect + 1, input[k], n_comp);
  655.    }
  656.    cc[1] = lohi;
  657.    cc[0] = lolo;
  658. }
  659.  
  660.  
  661. static void
  662. fxt1_quantize_ALPHA1 (GLuint *cc,
  663.                       GLubyte input[N_TEXELS][MAX_COMP])
  664. {
  665.    const GLint n_vect = 3; /* highest vector number in each microtile */
  666.    const GLint n_comp = 4; /* 4 components: R, G, B, A */
  667.    GLfloat vec[1 + 1 + 1][MAX_COMP]; /* 1.5 extrema for each sub-block */
  668.    GLfloat b, iv[MAX_COMP]; /* interpolation vector */
  669.    GLint i, j, k;
  670.    Fx64 hi; /* high quadword */
  671.    GLuint lohi, lolo; /* low quadword: hi dword, lo dword */
  672.  
  673.    GLint minSum;
  674.    GLint maxSum;
  675.    GLint minColL = 0, maxColL = 0;
  676.    GLint minColR = 0, maxColR = 0;
  677.    GLint sumL = 0, sumR = 0;
  678.    GLint nn_comp;
  679.    /* Our solution here is to find the darkest and brightest colors in
  680.     * the 4x4 tile and use those as the two representative colors.
  681.     * There are probably better algorithms to use (histogram-based).
  682.     */
  683.    nn_comp = n_comp;
  684.    while ((minColL == maxColL) && nn_comp) {
  685.        minSum = 2000; /* big enough */
  686.        maxSum = -1; /* small enough */
  687.        for (k = 0; k < N_TEXELS / 2; k++) {
  688.            GLint sum = 0;
  689.            for (i = 0; i < nn_comp; i++) {
  690.                sum += input[k][i];
  691.            }
  692.            if (minSum > sum) {
  693.                minSum = sum;
  694.                minColL = k;
  695.            }
  696.            if (maxSum < sum) {
  697.                maxSum = sum;
  698.                maxColL = k;
  699.            }
  700.            sumL += sum;
  701.        }
  702.        
  703.        nn_comp--;
  704.    }
  705.  
  706.    nn_comp = n_comp;
  707.    while ((minColR == maxColR) && nn_comp) {
  708.        minSum = 2000; /* big enough */
  709.        maxSum = -1; /* small enough */
  710.        for (k = N_TEXELS / 2; k < N_TEXELS; k++) {
  711.            GLint sum = 0;
  712.            for (i = 0; i < nn_comp; i++) {
  713.                sum += input[k][i];
  714.            }
  715.            if (minSum > sum) {
  716.                minSum = sum;
  717.                minColR = k;
  718.            }
  719.            if (maxSum < sum) {
  720.                maxSum = sum;
  721.                maxColR = k;
  722.            }
  723.            sumR += sum;
  724.        }
  725.  
  726.        nn_comp--;
  727.    }
  728.  
  729.    /* choose the common vector (yuck!) */
  730.    {
  731.       GLint j1, j2;
  732.       GLint v1 = 0, v2 = 0;
  733.       GLfloat err = 1e9; /* big enough */
  734.       GLfloat tv[2 * 2][MAX_COMP]; /* 2 extrema for each sub-block */
  735.       for (i = 0; i < n_comp; i++) {
  736.          tv[0][i] = input[minColL][i];
  737.          tv[1][i] = input[maxColL][i];
  738.          tv[2][i] = input[minColR][i];
  739.          tv[3][i] = input[maxColR][i];
  740.       }
  741.       for (j1 = 0; j1 < 2; j1++) {
  742.          for (j2 = 2; j2 < 4; j2++) {
  743.             GLfloat e = 0.0F;
  744.             for (i = 0; i < n_comp; i++) {
  745.                e += (tv[j1][i] - tv[j2][i]) * (tv[j1][i] - tv[j2][i]);
  746.             }
  747.             if (e < err) {
  748.                err = e;
  749.                v1 = j1;
  750.                v2 = j2;
  751.             }
  752.          }
  753.       }
  754.       for (i = 0; i < n_comp; i++) {
  755.          vec[0][i] = tv[1 - v1][i];
  756.          vec[1][i] = (tv[v1][i] * sumL + tv[v2][i] * sumR) / (sumL + sumR);
  757.          vec[2][i] = tv[5 - v2][i];
  758.       }
  759.    }
  760.  
  761.    /* left microtile */
  762.    cc[0] = 0;
  763.    if (minColL != maxColL) {
  764.       /* compute interpolation vector */
  765.       MAKEIVEC(n_vect, n_comp, iv, b, vec[0], vec[1]);
  766.  
  767.       /* add in texels */
  768.       lolo = 0;
  769.       for (k = N_TEXELS / 2 - 1; k >= 0; k--) {
  770.          GLint texel;
  771.          /* interpolate color */
  772.          CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
  773.          /* add in texel */
  774.          lolo <<= 2;
  775.          lolo |= texel;
  776.       }
  777.      
  778.       cc[0] = lolo;
  779.    }
  780.  
  781.    /* right microtile */
  782.    cc[1] = 0;
  783.    if (minColR != maxColR) {
  784.       /* compute interpolation vector */
  785.       MAKEIVEC(n_vect, n_comp, iv, b, vec[2], vec[1]);
  786.  
  787.       /* add in texels */
  788.       lohi = 0;
  789.       for (k = N_TEXELS - 1; k >= N_TEXELS / 2; k--) {
  790.          GLint texel;
  791.          /* interpolate color */
  792.          CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
  793.          /* add in texel */
  794.          lohi <<= 2;
  795.          lohi |= texel;
  796.       }
  797.  
  798.       cc[1] = lohi;
  799.    }
  800.  
  801.    FX64_MOV32(hi, 7); /* alpha = "011" + lerp = 1 */
  802.    for (j = n_vect - 1; j >= 0; j--) {
  803.       /* add in alphas */
  804.       FX64_SHL(hi, 5);
  805.       FX64_OR32(hi, (GLuint)(vec[j][ACOMP] / 8.0F));
  806.    }
  807.    for (j = n_vect - 1; j >= 0; j--) {
  808.       for (i = 0; i < n_comp - 1; i++) {
  809.          /* add in colors */
  810.          FX64_SHL(hi, 5);
  811.          FX64_OR32(hi, (GLuint)(vec[j][i] / 8.0F));
  812.       }
  813.    }
  814.    ((Fx64 *)cc)[1] = hi;
  815. }
  816.  
  817.  
  818. static void
  819. fxt1_quantize_HI (GLuint *cc,
  820.                   GLubyte input[N_TEXELS][MAX_COMP],
  821.                   GLubyte reord[N_TEXELS][MAX_COMP], GLint n)
  822. {
  823.    const GLint n_vect = 6; /* highest vector number */
  824.    const GLint n_comp = 3; /* 3 components: R, G, B */
  825.    GLfloat b = 0.0F;       /* phoudoin: silent compiler! */
  826.    GLfloat iv[MAX_COMP];   /* interpolation vector */
  827.    GLint i, k;
  828.    GLuint hihi; /* high quadword: hi dword */
  829.  
  830.    GLint minSum = 2000; /* big enough */
  831.    GLint maxSum = -1; /* small enough */
  832.    GLint minCol = 0; /* phoudoin: silent compiler! */
  833.    GLint maxCol = 0; /* phoudoin: silent compiler! */
  834.  
  835.    /* Our solution here is to find the darkest and brightest colors in
  836.     * the 8x4 tile and use those as the two representative colors.
  837.     * There are probably better algorithms to use (histogram-based).
  838.     */
  839.    for (k = 0; k < n; k++) {
  840.       GLint sum = 0;
  841.       for (i = 0; i < n_comp; i++) {
  842.          sum += reord[k][i];
  843.       }
  844.       if (minSum > sum) {
  845.          minSum = sum;
  846.          minCol = k;
  847.       }
  848.       if (maxSum < sum) {
  849.          maxSum = sum;
  850.          maxCol = k;
  851.       }
  852.    }
  853.  
  854.    hihi = 0; /* cc-hi = "00" */
  855.    for (i = 0; i < n_comp; i++) {
  856.       /* add in colors */
  857.       hihi <<= 5;
  858.       hihi |= reord[maxCol][i] >> 3;
  859.    }
  860.    for (i = 0; i < n_comp; i++) {
  861.       /* add in colors */
  862.       hihi <<= 5;
  863.       hihi |= reord[minCol][i] >> 3;
  864.    }
  865.    cc[3] = hihi;
  866.    cc[0] = cc[1] = cc[2] = 0;
  867.  
  868.    /* compute interpolation vector */
  869.    if (minCol != maxCol) {
  870.       MAKEIVEC(n_vect, n_comp, iv, b, reord[minCol], reord[maxCol]);
  871.    }
  872.  
  873.    /* add in texels */
  874.    for (k = N_TEXELS - 1; k >= 0; k--) {
  875.       GLint t = k * 3;
  876.       GLuint *kk = (GLuint *)((char *)cc + t / 8);
  877.       GLint texel = n_vect + 1; /* transparent black */
  878.  
  879.       if (!ISTBLACK(input[k])) {
  880.          if (minCol != maxCol) {
  881.             /* interpolate color */
  882.             CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
  883.             /* add in texel */
  884.             kk[0] |= texel << (t & 7);
  885.          }
  886.       } else {
  887.          /* add in texel */
  888.          kk[0] |= texel << (t & 7);
  889.       }
  890.    }
  891. }
  892.  
  893.  
  894. static void
  895. fxt1_quantize_MIXED1 (GLuint *cc,
  896.                       GLubyte input[N_TEXELS][MAX_COMP])
  897. {
  898.    const GLint n_vect = 2; /* highest vector number in each microtile */
  899.    const GLint n_comp = 3; /* 3 components: R, G, B */
  900.    GLubyte vec[2 * 2][MAX_COMP]; /* 2 extrema for each sub-block */
  901.    GLfloat b, iv[MAX_COMP]; /* interpolation vector */
  902.    GLint i, j, k;
  903.    Fx64 hi; /* high quadword */
  904.    GLuint lohi, lolo; /* low quadword: hi dword, lo dword */
  905.  
  906.    GLint minSum;
  907.    GLint maxSum;
  908.    GLint minColL = 0, maxColL = -1;
  909.    GLint minColR = 0, maxColR = -1;
  910.  
  911.    /* Our solution here is to find the darkest and brightest colors in
  912.     * the 4x4 tile and use those as the two representative colors.
  913.     * There are probably better algorithms to use (histogram-based).
  914.     */
  915.    minSum = 2000; /* big enough */
  916.    maxSum = -1; /* small enough */
  917.    for (k = 0; k < N_TEXELS / 2; k++) {
  918.       if (!ISTBLACK(input[k])) {
  919.          GLint sum = 0;
  920.          for (i = 0; i < n_comp; i++) {
  921.             sum += input[k][i];
  922.          }
  923.          if (minSum > sum) {
  924.             minSum = sum;
  925.             minColL = k;
  926.          }
  927.          if (maxSum < sum) {
  928.             maxSum = sum;
  929.             maxColL = k;
  930.          }
  931.       }
  932.    }
  933.    minSum = 2000; /* big enough */
  934.    maxSum = -1; /* small enough */
  935.    for (; k < N_TEXELS; k++) {
  936.       if (!ISTBLACK(input[k])) {
  937.          GLint sum = 0;
  938.          for (i = 0; i < n_comp; i++) {
  939.             sum += input[k][i];
  940.          }
  941.          if (minSum > sum) {
  942.             minSum = sum;
  943.             minColR = k;
  944.          }
  945.          if (maxSum < sum) {
  946.             maxSum = sum;
  947.             maxColR = k;
  948.          }
  949.       }
  950.    }
  951.  
  952.    /* left microtile */
  953.    if (maxColL == -1) {
  954.       /* all transparent black */
  955.       cc[0] = ~0u;
  956.       for (i = 0; i < n_comp; i++) {
  957.          vec[0][i] = 0;
  958.          vec[1][i] = 0;
  959.       }
  960.    } else {
  961.       cc[0] = 0;
  962.       for (i = 0; i < n_comp; i++) {
  963.          vec[0][i] = input[minColL][i];
  964.          vec[1][i] = input[maxColL][i];
  965.       }
  966.       if (minColL != maxColL) {
  967.          /* compute interpolation vector */
  968.          MAKEIVEC(n_vect, n_comp, iv, b, vec[0], vec[1]);
  969.  
  970.          /* add in texels */
  971.          lolo = 0;
  972.          for (k = N_TEXELS / 2 - 1; k >= 0; k--) {
  973.             GLint texel = n_vect + 1; /* transparent black */
  974.             if (!ISTBLACK(input[k])) {
  975.                /* interpolate color */
  976.                CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
  977.             }
  978.             /* add in texel */
  979.             lolo <<= 2;
  980.             lolo |= texel;
  981.          }
  982.          cc[0] = lolo;
  983.       }
  984.    }
  985.  
  986.    /* right microtile */
  987.    if (maxColR == -1) {
  988.       /* all transparent black */
  989.       cc[1] = ~0u;
  990.       for (i = 0; i < n_comp; i++) {
  991.          vec[2][i] = 0;
  992.          vec[3][i] = 0;
  993.       }
  994.    } else {
  995.       cc[1] = 0;
  996.       for (i = 0; i < n_comp; i++) {
  997.          vec[2][i] = input[minColR][i];
  998.          vec[3][i] = input[maxColR][i];
  999.       }
  1000.       if (minColR != maxColR) {
  1001.          /* compute interpolation vector */
  1002.          MAKEIVEC(n_vect, n_comp, iv, b, vec[2], vec[3]);
  1003.  
  1004.          /* add in texels */
  1005.          lohi = 0;
  1006.          for (k = N_TEXELS - 1; k >= N_TEXELS / 2; k--) {
  1007.             GLint texel = n_vect + 1; /* transparent black */
  1008.             if (!ISTBLACK(input[k])) {
  1009.                /* interpolate color */
  1010.                CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
  1011.             }
  1012.             /* add in texel */
  1013.             lohi <<= 2;
  1014.             lohi |= texel;
  1015.          }
  1016.          cc[1] = lohi;
  1017.       }
  1018.    }
  1019.  
  1020.    FX64_MOV32(hi, 9 | (vec[3][GCOMP] & 4) | ((vec[1][GCOMP] >> 1) & 2)); /* chroma = "1" */
  1021.    for (j = 2 * 2 - 1; j >= 0; j--) {
  1022.       for (i = 0; i < n_comp; i++) {
  1023.          /* add in colors */
  1024.          FX64_SHL(hi, 5);
  1025.          FX64_OR32(hi, vec[j][i] >> 3);
  1026.       }
  1027.    }
  1028.    ((Fx64 *)cc)[1] = hi;
  1029. }
  1030.  
  1031.  
  1032. static void
  1033. fxt1_quantize_MIXED0 (GLuint *cc,
  1034.                       GLubyte input[N_TEXELS][MAX_COMP])
  1035. {
  1036.    const GLint n_vect = 3; /* highest vector number in each microtile */
  1037.    const GLint n_comp = 3; /* 3 components: R, G, B */
  1038.    GLubyte vec[2 * 2][MAX_COMP]; /* 2 extrema for each sub-block */
  1039.    GLfloat b, iv[MAX_COMP]; /* interpolation vector */
  1040.    GLint i, j, k;
  1041.    Fx64 hi; /* high quadword */
  1042.    GLuint lohi, lolo; /* low quadword: hi dword, lo dword */
  1043.  
  1044.    GLint minColL = 0, maxColL = 0;
  1045.    GLint minColR = 0, maxColR = 0;
  1046. #if 0
  1047.    GLint minSum;
  1048.    GLint maxSum;
  1049.  
  1050.    /* Our solution here is to find the darkest and brightest colors in
  1051.     * the 4x4 tile and use those as the two representative colors.
  1052.     * There are probably better algorithms to use (histogram-based).
  1053.     */
  1054.    minSum = 2000; /* big enough */
  1055.    maxSum = -1; /* small enough */
  1056.    for (k = 0; k < N_TEXELS / 2; k++) {
  1057.       GLint sum = 0;
  1058.       for (i = 0; i < n_comp; i++) {
  1059.          sum += input[k][i];
  1060.       }
  1061.       if (minSum > sum) {
  1062.          minSum = sum;
  1063.          minColL = k;
  1064.       }
  1065.       if (maxSum < sum) {
  1066.          maxSum = sum;
  1067.          maxColL = k;
  1068.       }
  1069.    }
  1070.    minSum = 2000; /* big enough */
  1071.    maxSum = -1; /* small enough */
  1072.    for (; k < N_TEXELS; k++) {
  1073.       GLint sum = 0;
  1074.       for (i = 0; i < n_comp; i++) {
  1075.          sum += input[k][i];
  1076.       }
  1077.       if (minSum > sum) {
  1078.          minSum = sum;
  1079.          minColR = k;
  1080.       }
  1081.       if (maxSum < sum) {
  1082.          maxSum = sum;
  1083.          maxColR = k;
  1084.       }
  1085.    }
  1086. #else
  1087.    GLint minVal;
  1088.    GLint maxVal;
  1089.    GLint maxVarL = fxt1_variance(NULL, input, n_comp, N_TEXELS / 2);
  1090.    GLint maxVarR = fxt1_variance(NULL, &input[N_TEXELS / 2], n_comp, N_TEXELS / 2);
  1091.  
  1092.    /* Scan the channel with max variance for lo & hi
  1093.     * and use those as the two representative colors.
  1094.     */
  1095.    minVal = 2000; /* big enough */
  1096.    maxVal = -1; /* small enough */
  1097.    for (k = 0; k < N_TEXELS / 2; k++) {
  1098.       GLint t = input[k][maxVarL];
  1099.       if (minVal > t) {
  1100.          minVal = t;
  1101.          minColL = k;
  1102.       }
  1103.       if (maxVal < t) {
  1104.          maxVal = t;
  1105.          maxColL = k;
  1106.       }
  1107.    }
  1108.    minVal = 2000; /* big enough */
  1109.    maxVal = -1; /* small enough */
  1110.    for (; k < N_TEXELS; k++) {
  1111.       GLint t = input[k][maxVarR];
  1112.       if (minVal > t) {
  1113.          minVal = t;
  1114.          minColR = k;
  1115.       }
  1116.       if (maxVal < t) {
  1117.          maxVal = t;
  1118.          maxColR = k;
  1119.       }
  1120.    }
  1121. #endif
  1122.  
  1123.    /* left microtile */
  1124.    cc[0] = 0;
  1125.    for (i = 0; i < n_comp; i++) {
  1126.       vec[0][i] = input[minColL][i];
  1127.       vec[1][i] = input[maxColL][i];
  1128.    }
  1129.    if (minColL != maxColL) {
  1130.       /* compute interpolation vector */
  1131.       MAKEIVEC(n_vect, n_comp, iv, b, vec[0], vec[1]);
  1132.  
  1133.       /* add in texels */
  1134.       lolo = 0;
  1135.       for (k = N_TEXELS / 2 - 1; k >= 0; k--) {
  1136.          GLint texel;
  1137.          /* interpolate color */
  1138.          CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
  1139.          /* add in texel */
  1140.          lolo <<= 2;
  1141.          lolo |= texel;
  1142.       }
  1143.  
  1144.       /* funky encoding for LSB of green */
  1145.       if ((GLint)((lolo >> 1) & 1) != (((vec[1][GCOMP] ^ vec[0][GCOMP]) >> 2) & 1)) {
  1146.          for (i = 0; i < n_comp; i++) {
  1147.             vec[1][i] = input[minColL][i];
  1148.             vec[0][i] = input[maxColL][i];
  1149.          }
  1150.          lolo = ~lolo;
  1151.       }
  1152.      
  1153.       cc[0] = lolo;
  1154.    }
  1155.  
  1156.    /* right microtile */
  1157.    cc[1] = 0;
  1158.    for (i = 0; i < n_comp; i++) {
  1159.       vec[2][i] = input[minColR][i];
  1160.       vec[3][i] = input[maxColR][i];
  1161.    }
  1162.    if (minColR != maxColR) {
  1163.       /* compute interpolation vector */
  1164.       MAKEIVEC(n_vect, n_comp, iv, b, vec[2], vec[3]);
  1165.  
  1166.       /* add in texels */
  1167.       lohi = 0;
  1168.       for (k = N_TEXELS - 1; k >= N_TEXELS / 2; k--) {
  1169.          GLint texel;
  1170.          /* interpolate color */
  1171.          CALCCDOT(texel, n_vect, n_comp, iv, b, input[k]);
  1172.          /* add in texel */
  1173.          lohi <<= 2;
  1174.          lohi |= texel;
  1175.       }
  1176.  
  1177.       /* funky encoding for LSB of green */
  1178.       if ((GLint)((lohi >> 1) & 1) != (((vec[3][GCOMP] ^ vec[2][GCOMP]) >> 2) & 1)) {
  1179.          for (i = 0; i < n_comp; i++) {
  1180.             vec[3][i] = input[minColR][i];
  1181.             vec[2][i] = input[maxColR][i];
  1182.          }
  1183.          lohi = ~lohi;
  1184.       }
  1185.  
  1186.       cc[1] = lohi;
  1187.    }
  1188.  
  1189.    FX64_MOV32(hi, 8 | (vec[3][GCOMP] & 4) | ((vec[1][GCOMP] >> 1) & 2)); /* chroma = "1" */
  1190.    for (j = 2 * 2 - 1; j >= 0; j--) {
  1191.       for (i = 0; i < n_comp; i++) {
  1192.          /* add in colors */
  1193.          FX64_SHL(hi, 5);
  1194.          FX64_OR32(hi, vec[j][i] >> 3);
  1195.       }
  1196.    }
  1197.    ((Fx64 *)cc)[1] = hi;
  1198. }
  1199.  
  1200.  
  1201. static void
  1202. fxt1_quantize (GLuint *cc, const GLubyte *lines[], GLint comps)
  1203. {
  1204.    GLint trualpha;
  1205.    GLubyte reord[N_TEXELS][MAX_COMP];
  1206.  
  1207.    GLubyte input[N_TEXELS][MAX_COMP];
  1208.    GLint i, k, l;
  1209.  
  1210.    if (comps == 3) {
  1211.       /* make the whole block opaque */
  1212.       memset(input, -1, sizeof(input));
  1213.    }
  1214.  
  1215.    /* 8 texels each line */
  1216.    for (l = 0; l < 4; l++) {
  1217.       for (k = 0; k < 4; k++) {
  1218.          for (i = 0; i < comps; i++) {
  1219.             input[k + l * 4][i] = *lines[l]++;
  1220.          }
  1221.       }
  1222.       for (; k < 8; k++) {
  1223.          for (i = 0; i < comps; i++) {
  1224.             input[k + l * 4 + 12][i] = *lines[l]++;
  1225.          }
  1226.       }
  1227.    }
  1228.  
  1229.    /* block layout:
  1230.     * 00, 01, 02, 03, 08, 09, 0a, 0b
  1231.     * 10, 11, 12, 13, 18, 19, 1a, 1b
  1232.     * 04, 05, 06, 07, 0c, 0d, 0e, 0f
  1233.     * 14, 15, 16, 17, 1c, 1d, 1e, 1f
  1234.     */
  1235.  
  1236.    /* [dBorca]
  1237.     * stupidity flows forth from this
  1238.     */
  1239.    l = N_TEXELS;
  1240.    trualpha = 0;
  1241.    if (comps == 4) {
  1242.       /* skip all transparent black texels */
  1243.       l = 0;
  1244.       for (k = 0; k < N_TEXELS; k++) {
  1245.          /* test all components against 0 */
  1246.          if (!ISTBLACK(input[k])) {
  1247.             /* texel is not transparent black */
  1248.             COPY_4UBV(reord[l], input[k]);
  1249.             if (reord[l][ACOMP] < (255 - ALPHA_TS)) {
  1250.                /* non-opaque texel */
  1251.                trualpha = !0;
  1252.             }
  1253.             l++;
  1254.          }
  1255.       }
  1256.    }
  1257.  
  1258. #if 0
  1259.    if (trualpha) {
  1260.       fxt1_quantize_ALPHA0(cc, input, reord, l);
  1261.    } else if (l == 0) {
  1262.       cc[0] = cc[1] = cc[2] = -1;
  1263.       cc[3] = 0;
  1264.    } else if (l < N_TEXELS) {
  1265.       fxt1_quantize_HI(cc, input, reord, l);
  1266.    } else {
  1267.       fxt1_quantize_CHROMA(cc, input);
  1268.    }
  1269.    (void)fxt1_quantize_ALPHA1;
  1270.    (void)fxt1_quantize_MIXED1;
  1271.    (void)fxt1_quantize_MIXED0;
  1272. #else
  1273.    if (trualpha) {
  1274.       fxt1_quantize_ALPHA1(cc, input);
  1275.    } else if (l == 0) {
  1276.       cc[0] = cc[1] = cc[2] = ~0u;
  1277.       cc[3] = 0;
  1278.    } else if (l < N_TEXELS) {
  1279.       fxt1_quantize_MIXED1(cc, input);
  1280.    } else {
  1281.       fxt1_quantize_MIXED0(cc, input);
  1282.    }
  1283.    (void)fxt1_quantize_ALPHA0;
  1284.    (void)fxt1_quantize_HI;
  1285.    (void)fxt1_quantize_CHROMA;
  1286. #endif
  1287. }
  1288.  
  1289.  
  1290. static void
  1291. fxt1_encode (GLuint width, GLuint height, GLint comps,
  1292.              const void *source, GLint srcRowStride,
  1293.              void *dest, GLint destRowStride)
  1294. {
  1295.    GLuint x, y;
  1296.    const GLubyte *data;
  1297.    GLuint *encoded = (GLuint *)dest;
  1298.    void *newSource = NULL;
  1299.  
  1300.    assert(comps == 3 || comps == 4);
  1301.  
  1302.    /* Replicate image if width is not M8 or height is not M4 */
  1303.    if ((width & 7) | (height & 3)) {
  1304.       GLint newWidth = (width + 7) & ~7;
  1305.       GLint newHeight = (height + 3) & ~3;
  1306.       newSource = malloc(comps * newWidth * newHeight * sizeof(GLchan));
  1307.       if (!newSource) {
  1308.          GET_CURRENT_CONTEXT(ctx);
  1309.          _mesa_error(ctx, GL_OUT_OF_MEMORY, "texture compression");
  1310.          goto cleanUp;
  1311.       }
  1312.       _mesa_upscale_teximage2d(width, height, newWidth, newHeight,
  1313.                                comps, (const GLchan *) source,
  1314.                                srcRowStride, (GLchan *) newSource);
  1315.       source = newSource;
  1316.       width = newWidth;
  1317.       height = newHeight;
  1318.       srcRowStride = comps * newWidth;
  1319.    }
  1320.  
  1321.    /* convert from 16/32-bit channels to GLubyte if needed */
  1322.    if (CHAN_TYPE != GL_UNSIGNED_BYTE) {
  1323.       const GLuint n = width * height * comps;
  1324.       const GLchan *src = (const GLchan *) source;
  1325.       GLubyte *dest = (GLubyte *) malloc(n * sizeof(GLubyte));
  1326.       GLuint i;
  1327.       if (!dest) {
  1328.          GET_CURRENT_CONTEXT(ctx);
  1329.          _mesa_error(ctx, GL_OUT_OF_MEMORY, "texture compression");
  1330.          goto cleanUp;
  1331.       }
  1332.       for (i = 0; i < n; i++) {
  1333.          dest[i] = CHAN_TO_UBYTE(src[i]);
  1334.       }
  1335.       if (newSource != NULL) {
  1336.          free(newSource);
  1337.       }
  1338.       newSource = dest;  /* we'll free this buffer before returning */
  1339.       source = dest;  /* the new, GLubyte incoming image */
  1340.    }
  1341.  
  1342.    data = (const GLubyte *) source;
  1343.    destRowStride = (destRowStride - width * 2) / 4;
  1344.    for (y = 0; y < height; y += 4) {
  1345.       GLuint offs = 0 + (y + 0) * srcRowStride;
  1346.       for (x = 0; x < width; x += 8) {
  1347.          const GLubyte *lines[4];
  1348.          lines[0] = &data[offs];
  1349.          lines[1] = lines[0] + srcRowStride;
  1350.          lines[2] = lines[1] + srcRowStride;
  1351.          lines[3] = lines[2] + srcRowStride;
  1352.          offs += 8 * comps;
  1353.          fxt1_quantize(encoded, lines, comps);
  1354.          /* 128 bits per 8x4 block */
  1355.          encoded += 4;
  1356.       }
  1357.       encoded += destRowStride;
  1358.    }
  1359.  
  1360.  cleanUp:
  1361.    if (newSource != NULL) {
  1362.       free(newSource);
  1363.    }
  1364. }
  1365.  
  1366.  
  1367. /***************************************************************************\
  1368.  * FXT1 decoder
  1369.  *
  1370.  * The decoder is based on GL_3DFX_texture_compression_FXT1
  1371.  * specification and serves as a concept for the encoder.
  1372. \***************************************************************************/
  1373.  
  1374.  
  1375. /* lookup table for scaling 5 bit colors up to 8 bits */
  1376. static const GLubyte _rgb_scale_5[] = {
  1377.    0,   8,   16,  25,  33,  41,  49,  58,
  1378.    66,  74,  82,  90,  99,  107, 115, 123,
  1379.    132, 140, 148, 156, 165, 173, 181, 189,
  1380.    197, 206, 214, 222, 230, 239, 247, 255
  1381. };
  1382.  
  1383. /* lookup table for scaling 6 bit colors up to 8 bits */
  1384. static const GLubyte _rgb_scale_6[] = {
  1385.    0,   4,   8,   12,  16,  20,  24,  28,
  1386.    32,  36,  40,  45,  49,  53,  57,  61,
  1387.    65,  69,  73,  77,  81,  85,  89,  93,
  1388.    97,  101, 105, 109, 113, 117, 121, 125,
  1389.    130, 134, 138, 142, 146, 150, 154, 158,
  1390.    162, 166, 170, 174, 178, 182, 186, 190,
  1391.    194, 198, 202, 206, 210, 215, 219, 223,
  1392.    227, 231, 235, 239, 243, 247, 251, 255
  1393. };
  1394.  
  1395.  
  1396. #define CC_SEL(cc, which) (((GLuint *)(cc))[(which) / 32] >> ((which) & 31))
  1397. #define UP5(c) _rgb_scale_5[(c) & 31]
  1398. #define UP6(c, b) _rgb_scale_6[(((c) & 31) << 1) | ((b) & 1)]
  1399. #define LERP(n, t, c0, c1) (((n) - (t)) * (c0) + (t) * (c1) + (n) / 2) / (n)
  1400.  
  1401.  
  1402. static void
  1403. fxt1_decode_1HI (const GLubyte *code, GLint t, GLchan *rgba)
  1404. {
  1405.    const GLuint *cc;
  1406.  
  1407.    t *= 3;
  1408.    cc = (const GLuint *)(code + t / 8);
  1409.    t = (cc[0] >> (t & 7)) & 7;
  1410.  
  1411.    if (t == 7) {
  1412.       rgba[RCOMP] = rgba[GCOMP] = rgba[BCOMP] = rgba[ACOMP] = 0;
  1413.    } else {
  1414.       GLubyte r, g, b;
  1415.       cc = (const GLuint *)(code + 12);
  1416.       if (t == 0) {
  1417.          b = UP5(CC_SEL(cc, 0));
  1418.          g = UP5(CC_SEL(cc, 5));
  1419.          r = UP5(CC_SEL(cc, 10));
  1420.       } else if (t == 6) {
  1421.          b = UP5(CC_SEL(cc, 15));
  1422.          g = UP5(CC_SEL(cc, 20));
  1423.          r = UP5(CC_SEL(cc, 25));
  1424.       } else {
  1425.          b = LERP(6, t, UP5(CC_SEL(cc, 0)), UP5(CC_SEL(cc, 15)));
  1426.          g = LERP(6, t, UP5(CC_SEL(cc, 5)), UP5(CC_SEL(cc, 20)));
  1427.          r = LERP(6, t, UP5(CC_SEL(cc, 10)), UP5(CC_SEL(cc, 25)));
  1428.       }
  1429.       rgba[RCOMP] = UBYTE_TO_CHAN(r);
  1430.       rgba[GCOMP] = UBYTE_TO_CHAN(g);
  1431.       rgba[BCOMP] = UBYTE_TO_CHAN(b);
  1432.       rgba[ACOMP] = CHAN_MAX;
  1433.    }
  1434. }
  1435.  
  1436.  
  1437. static void
  1438. fxt1_decode_1CHROMA (const GLubyte *code, GLint t, GLchan *rgba)
  1439. {
  1440.    const GLuint *cc;
  1441.    GLuint kk;
  1442.  
  1443.    cc = (const GLuint *)code;
  1444.    if (t & 16) {
  1445.       cc++;
  1446.       t &= 15;
  1447.    }
  1448.    t = (cc[0] >> (t * 2)) & 3;
  1449.  
  1450.    t *= 15;
  1451.    cc = (const GLuint *)(code + 8 + t / 8);
  1452.    kk = cc[0] >> (t & 7);
  1453.    rgba[BCOMP] = UBYTE_TO_CHAN( UP5(kk) );
  1454.    rgba[GCOMP] = UBYTE_TO_CHAN( UP5(kk >> 5) );
  1455.    rgba[RCOMP] = UBYTE_TO_CHAN( UP5(kk >> 10) );
  1456.    rgba[ACOMP] = CHAN_MAX;
  1457. }
  1458.  
  1459.  
  1460. static void
  1461. fxt1_decode_1MIXED (const GLubyte *code, GLint t, GLchan *rgba)
  1462. {
  1463.    const GLuint *cc;
  1464.    GLuint col[2][3];
  1465.    GLint glsb, selb;
  1466.  
  1467.    cc = (const GLuint *)code;
  1468.    if (t & 16) {
  1469.       t &= 15;
  1470.       t = (cc[1] >> (t * 2)) & 3;
  1471.       /* col 2 */
  1472.       col[0][BCOMP] = (*(const GLuint *)(code + 11)) >> 6;
  1473.       col[0][GCOMP] = CC_SEL(cc, 99);
  1474.       col[0][RCOMP] = CC_SEL(cc, 104);
  1475.       /* col 3 */
  1476.       col[1][BCOMP] = CC_SEL(cc, 109);
  1477.       col[1][GCOMP] = CC_SEL(cc, 114);
  1478.       col[1][RCOMP] = CC_SEL(cc, 119);
  1479.       glsb = CC_SEL(cc, 126);
  1480.       selb = CC_SEL(cc, 33);
  1481.    } else {
  1482.       t = (cc[0] >> (t * 2)) & 3;
  1483.       /* col 0 */
  1484.       col[0][BCOMP] = CC_SEL(cc, 64);
  1485.       col[0][GCOMP] = CC_SEL(cc, 69);
  1486.       col[0][RCOMP] = CC_SEL(cc, 74);
  1487.       /* col 1 */
  1488.       col[1][BCOMP] = CC_SEL(cc, 79);
  1489.       col[1][GCOMP] = CC_SEL(cc, 84);
  1490.       col[1][RCOMP] = CC_SEL(cc, 89);
  1491.       glsb = CC_SEL(cc, 125);
  1492.       selb = CC_SEL(cc, 1);
  1493.    }
  1494.  
  1495.    if (CC_SEL(cc, 124) & 1) {
  1496.       /* alpha[0] == 1 */
  1497.  
  1498.       if (t == 3) {
  1499.          /* zero */
  1500.          rgba[RCOMP] = rgba[BCOMP] = rgba[GCOMP] = rgba[ACOMP] = 0;
  1501.       } else {
  1502.          GLubyte r, g, b;
  1503.          if (t == 0) {
  1504.             b = UP5(col[0][BCOMP]);
  1505.             g = UP5(col[0][GCOMP]);
  1506.             r = UP5(col[0][RCOMP]);
  1507.          } else if (t == 2) {
  1508.             b = UP5(col[1][BCOMP]);
  1509.             g = UP6(col[1][GCOMP], glsb);
  1510.             r = UP5(col[1][RCOMP]);
  1511.          } else {
  1512.             b = (UP5(col[0][BCOMP]) + UP5(col[1][BCOMP])) / 2;
  1513.             g = (UP5(col[0][GCOMP]) + UP6(col[1][GCOMP], glsb)) / 2;
  1514.             r = (UP5(col[0][RCOMP]) + UP5(col[1][RCOMP])) / 2;
  1515.          }
  1516.          rgba[RCOMP] = UBYTE_TO_CHAN(r);
  1517.          rgba[GCOMP] = UBYTE_TO_CHAN(g);
  1518.          rgba[BCOMP] = UBYTE_TO_CHAN(b);
  1519.          rgba[ACOMP] = CHAN_MAX;
  1520.       }
  1521.    } else {
  1522.       /* alpha[0] == 0 */
  1523.       GLubyte r, g, b;
  1524.       if (t == 0) {
  1525.          b = UP5(col[0][BCOMP]);
  1526.          g = UP6(col[0][GCOMP], glsb ^ selb);
  1527.          r = UP5(col[0][RCOMP]);
  1528.       } else if (t == 3) {
  1529.          b = UP5(col[1][BCOMP]);
  1530.          g = UP6(col[1][GCOMP], glsb);
  1531.          r = UP5(col[1][RCOMP]);
  1532.       } else {
  1533.          b = LERP(3, t, UP5(col[0][BCOMP]), UP5(col[1][BCOMP]));
  1534.          g = LERP(3, t, UP6(col[0][GCOMP], glsb ^ selb),
  1535.                         UP6(col[1][GCOMP], glsb));
  1536.          r = LERP(3, t, UP5(col[0][RCOMP]), UP5(col[1][RCOMP]));
  1537.       }
  1538.       rgba[RCOMP] = UBYTE_TO_CHAN(r);
  1539.       rgba[GCOMP] = UBYTE_TO_CHAN(g);
  1540.       rgba[BCOMP] = UBYTE_TO_CHAN(b);
  1541.       rgba[ACOMP] = CHAN_MAX;
  1542.    }
  1543. }
  1544.  
  1545.  
  1546. static void
  1547. fxt1_decode_1ALPHA (const GLubyte *code, GLint t, GLchan *rgba)
  1548. {
  1549.    const GLuint *cc;
  1550.    GLubyte r, g, b, a;
  1551.  
  1552.    cc = (const GLuint *)code;
  1553.    if (CC_SEL(cc, 124) & 1) {
  1554.       /* lerp == 1 */
  1555.       GLuint col0[4];
  1556.  
  1557.       if (t & 16) {
  1558.          t &= 15;
  1559.          t = (cc[1] >> (t * 2)) & 3;
  1560.          /* col 2 */
  1561.          col0[BCOMP] = (*(const GLuint *)(code + 11)) >> 6;
  1562.          col0[GCOMP] = CC_SEL(cc, 99);
  1563.          col0[RCOMP] = CC_SEL(cc, 104);
  1564.          col0[ACOMP] = CC_SEL(cc, 119);
  1565.       } else {
  1566.          t = (cc[0] >> (t * 2)) & 3;
  1567.          /* col 0 */
  1568.          col0[BCOMP] = CC_SEL(cc, 64);
  1569.          col0[GCOMP] = CC_SEL(cc, 69);
  1570.          col0[RCOMP] = CC_SEL(cc, 74);
  1571.          col0[ACOMP] = CC_SEL(cc, 109);
  1572.       }
  1573.  
  1574.       if (t == 0) {
  1575.          b = UP5(col0[BCOMP]);
  1576.          g = UP5(col0[GCOMP]);
  1577.          r = UP5(col0[RCOMP]);
  1578.          a = UP5(col0[ACOMP]);
  1579.       } else if (t == 3) {
  1580.          b = UP5(CC_SEL(cc, 79));
  1581.          g = UP5(CC_SEL(cc, 84));
  1582.          r = UP5(CC_SEL(cc, 89));
  1583.          a = UP5(CC_SEL(cc, 114));
  1584.       } else {
  1585.          b = LERP(3, t, UP5(col0[BCOMP]), UP5(CC_SEL(cc, 79)));
  1586.          g = LERP(3, t, UP5(col0[GCOMP]), UP5(CC_SEL(cc, 84)));
  1587.          r = LERP(3, t, UP5(col0[RCOMP]), UP5(CC_SEL(cc, 89)));
  1588.          a = LERP(3, t, UP5(col0[ACOMP]), UP5(CC_SEL(cc, 114)));
  1589.       }
  1590.    } else {
  1591.       /* lerp == 0 */
  1592.  
  1593.       if (t & 16) {
  1594.          cc++;
  1595.          t &= 15;
  1596.       }
  1597.       t = (cc[0] >> (t * 2)) & 3;
  1598.  
  1599.       if (t == 3) {
  1600.          /* zero */
  1601.          r = g = b = a = 0;
  1602.       } else {
  1603.          GLuint kk;
  1604.          cc = (const GLuint *)code;
  1605.          a = UP5(cc[3] >> (t * 5 + 13));
  1606.          t *= 15;
  1607.          cc = (const GLuint *)(code + 8 + t / 8);
  1608.          kk = cc[0] >> (t & 7);
  1609.          b = UP5(kk);
  1610.          g = UP5(kk >> 5);
  1611.          r = UP5(kk >> 10);
  1612.       }
  1613.    }
  1614.    rgba[RCOMP] = UBYTE_TO_CHAN(r);
  1615.    rgba[GCOMP] = UBYTE_TO_CHAN(g);
  1616.    rgba[BCOMP] = UBYTE_TO_CHAN(b);
  1617.    rgba[ACOMP] = UBYTE_TO_CHAN(a);
  1618. }
  1619.  
  1620.  
  1621. void
  1622. fxt1_decode_1 (const void *texture, GLint stride, /* in pixels */
  1623.                GLint i, GLint j, GLchan *rgba)
  1624. {
  1625.    static void (*decode_1[]) (const GLubyte *, GLint, GLchan *) = {
  1626.       fxt1_decode_1HI,     /* cc-high   = "00?" */
  1627.       fxt1_decode_1HI,     /* cc-high   = "00?" */
  1628.       fxt1_decode_1CHROMA, /* cc-chroma = "010" */
  1629.       fxt1_decode_1ALPHA,  /* alpha     = "011" */
  1630.       fxt1_decode_1MIXED,  /* mixed     = "1??" */
  1631.       fxt1_decode_1MIXED,  /* mixed     = "1??" */
  1632.       fxt1_decode_1MIXED,  /* mixed     = "1??" */
  1633.       fxt1_decode_1MIXED   /* mixed     = "1??" */
  1634.    };
  1635.  
  1636.    const GLubyte *code = (const GLubyte *)texture +
  1637.                          ((j / 4) * (stride / 8) + (i / 8)) * 16;
  1638.    GLint mode = CC_SEL(code, 125);
  1639.    GLint t = i & 7;
  1640.  
  1641.    if (t & 4) {
  1642.       t += 12;
  1643.    }
  1644.    t += (j & 3) * 4;
  1645.  
  1646.    decode_1[mode](code, t, rgba);
  1647. }
  1648.  
  1649.  
  1650. #endif /* FEATURE_texture_fxt1 */
  1651.