← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/vnc4/gutsy

« back to all changes in this revision

Viewing changes to unix/xc/lib/Xmu/CmapAlloc.c

  • Committer: Bazaar Package Importer
  • Author(s): Ola Lundqvist
  • Date: 2006-05-15 20:35:17 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20060515203517-l4lre1ku942mn26k
Tags: 4.1.1+X4.3.0-10
* Correction of critical security issue. Thanks to Martin Kogler
  <e9925248@student.tuwien.ac.at> that informed me about the issue,
  and provided the patch.
  This flaw was originally found by Steve Wiseman of intelliadmin.com.
* Applied patch from Javier Kohen <jkohen@users.sourceforge.net> that
  inform the user that only 8 first characters of the password will
  actually be used when typing more than 8 characters, closes:
  #355619.

Show diffs side-by-side

added added

removed removed

Lines of Context:
unix/xc/lib/Xmu/CmapAlloc.c
 
1
/* $Xorg: CmapAlloc.c,v 1.4 2001/02/09 02:03:51 xorgcvs Exp $ */
 
2
 
 
3
/* 
 
4
 
 
5
Copyright 1989, 1994, 1998  The Open Group
 
6
 
 
7
Permission to use, copy, modify, distribute, and sell this software and its
 
8
documentation for any purpose is hereby granted without fee, provided that
 
9
the above copyright notice appear in all copies and that both that
 
10
copyright notice and this permission notice appear in supporting
 
11
documentation.
 
12
 
 
13
The above copyright notice and this permission notice shall be included in
 
14
all copies or substantial portions of the Software.
 
15
 
 
16
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 
17
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 
18
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 
19
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
 
20
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 
21
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 
22
 
 
23
Except as contained in this notice, the name of The Open Group shall not be
 
24
used in advertising or otherwise to promote the sale, use or other dealings
 
25
in this Software without prior written authorization from The Open Group.
 
26
 
 
27
*/
 
28
/* $XFree86: xc/lib/Xmu/CmapAlloc.c,v 1.7 2001/12/14 19:55:35 dawes Exp $ */
 
29
 
 
30
/*
 
31
 * Author:  Donna Converse, MIT X Consortium
 
32
 */
 
33
 
 
34
#include <X11/Xlib.h>
 
35
#include <X11/Xatom.h>
 
36
#include <X11/Xutil.h>
 
37
#include <X11/Xmu/StdCmap.h>
 
38
#include <stdio.h>
 
39
 
 
40
#define lowbit(x) ((x) & (~(x) + 1))
 
41
 
 
42
/*
 
43
 * Prototypes
 
44
 */
 
45
static void best_allocation(XVisualInfo*, unsigned long*, unsigned long*,
 
46
                            unsigned long*);
 
47
static int default_allocation(XVisualInfo*, unsigned long*,
 
48
                              unsigned long*, unsigned long*);
 
49
static void gray_allocation(int, unsigned long*, unsigned long*,
 
50
                            unsigned long*);
 
51
static int icbrt(int);
 
52
static int icbrt_with_bits(int, int);
 
53
static int icbrt_with_guess(int, int);
 
54
 
 
55
/* To determine the best allocation of reds, greens, and blues in a 
 
56
 * standard colormap, use XmuGetColormapAllocation.
 
57
 *      vinfo           specifies visual information for a chosen visual
 
58
 *      property        specifies one of the standard colormap property names
 
59
 *      red_max         returns maximum red value 
 
60
 *      green_max       returns maximum green value
 
61
 *      blue_max        returns maximum blue value
 
62
 *
 
63
 * XmuGetColormapAllocation returns 0 on failure, non-zero on success.
 
64
 * It is assumed that the visual is appropriate for the colormap property.
 
65
 */
 
66
 
 
67
Status
 
68
XmuGetColormapAllocation(XVisualInfo *vinfo, Atom property,
 
69
                         unsigned long *red_max,
 
70
                         unsigned long *green_max,
 
71
                         unsigned long *blue_max)
 
72
{
 
73
    Status      status = 1;
 
74
 
 
75
    if (vinfo->colormap_size <= 2)
 
76
        return 0;
 
77
 
 
78
    switch (property)
 
79
    {
 
80
      case XA_RGB_DEFAULT_MAP:
 
81
        status = default_allocation(vinfo, red_max, green_max, blue_max);
 
82
        break;
 
83
      case XA_RGB_BEST_MAP:
 
84
        best_allocation(vinfo, red_max, green_max, blue_max);
 
85
        break;
 
86
      case XA_RGB_GRAY_MAP:
 
87
        gray_allocation(vinfo->colormap_size, red_max, green_max, blue_max);
 
88
        break;
 
89
      case XA_RGB_RED_MAP:
 
90
        *red_max = vinfo->colormap_size - 1;
 
91
        *green_max = *blue_max = 0;
 
92
        break;
 
93
      case XA_RGB_GREEN_MAP:
 
94
        *green_max = vinfo->colormap_size - 1;
 
95
        *red_max = *blue_max = 0;
 
96
        break;
 
97
      case XA_RGB_BLUE_MAP:
 
98
        *blue_max = vinfo->colormap_size - 1;
 
99
        *red_max = *green_max = 0;
 
100
        break;
 
101
      default:
 
102
        status = 0;
 
103
    }
 
104
    return status;
 
105
}
 
106
 
 
107
/****************************************************************************/
 
108
/* Determine the appropriate color allocations of a gray scale.
 
109
 *
 
110
 * Keith Packard, MIT X Consortium
 
111
 */
 
112
 
 
113
static void
 
114
gray_allocation(int n, unsigned long *red_max, unsigned long *green_max,
 
115
                unsigned long *blue_max)
 
116
{
 
117
    *red_max = (n * 30) / 100;
 
118
    *green_max = (n * 59) / 100; 
 
119
    *blue_max = (n * 11) / 100; 
 
120
    *green_max += ((n - 1) - (*red_max + *green_max + *blue_max));
 
121
}
 
122
 
 
123
/****************************************************************************/
 
124
/* Determine an appropriate color allocation for the RGB_DEFAULT_MAP.
 
125
 * If a map has less than a minimum number of definable entries, we do not
 
126
 * produce an allocation for an RGB_DEFAULT_MAP.  
 
127
 *
 
128
 * For 16 planes, the default colormap will have 27 each RGB; for 12 planes,
 
129
 * 12 each.  For 8 planes, let n = the number of colormap entries, which may
 
130
 * be 256 or 254.  Then, maximum red value = floor(cube_root(n - 125)) - 1.
 
131
 * Maximum green and maximum blue values are identical to maximum red.
 
132
 * This leaves at least 125 cells which clients can allocate.
 
133
 *
 
134
 * Return 0 if an allocation has been determined, non-zero otherwise.
 
135
 */
 
136
 
 
137
static int
 
138
default_allocation(XVisualInfo *vinfo, unsigned long *red,
 
139
                   unsigned long *green, unsigned long *blue)
 
140
{
 
141
    int                 ngrays;         /* number of gray cells */
 
142
 
 
143
    switch (vinfo->class) {
 
144
      case PseudoColor:
 
145
 
 
146
        if (vinfo->colormap_size > 65000)
 
147
            /* intended for displays with 16 planes */
 
148
            *red = *green = *blue = (unsigned long) 27;
 
149
        else if (vinfo->colormap_size > 4000)
 
150
            /* intended for displays with 12 planes */
 
151
            *red = *green = *blue = (unsigned long) 12;
 
152
        else if (vinfo->colormap_size < 250)
 
153
            return 0;
 
154
        else
 
155
            /* intended for displays with 8 planes */
 
156
            *red = *green = *blue = (unsigned long)
 
157
                (icbrt(vinfo->colormap_size - 125) - 1);
 
158
        break;
 
159
 
 
160
      case DirectColor:
 
161
 
 
162
        if (vinfo->colormap_size < 10)
 
163
            return 0;
 
164
        *red = *green = *blue = vinfo->colormap_size / 2 - 1;
 
165
        break;
 
166
 
 
167
      case TrueColor:
 
168
 
 
169
        *red = vinfo->red_mask / lowbit(vinfo->red_mask);
 
170
        *green = vinfo->green_mask / lowbit(vinfo->green_mask);
 
171
        *blue = vinfo->blue_mask / lowbit(vinfo->blue_mask);
 
172
        break;
 
173
 
 
174
      case GrayScale:
 
175
 
 
176
        if (vinfo->colormap_size > 65000)
 
177
            ngrays = 4096;
 
178
        else if (vinfo->colormap_size > 4000)
 
179
            ngrays = 512;
 
180
        else if (vinfo->colormap_size < 250)
 
181
            return 0;
 
182
        else
 
183
            ngrays = 12;
 
184
        gray_allocation(ngrays, red, green, blue);
 
185
        break;
 
186
        
 
187
      default:
 
188
        return 0;
 
189
    }
 
190
    return 1;
 
191
}
 
192
 
 
193
/****************************************************************************/
 
194
/* Determine an appropriate color allocation for the RGB_BEST_MAP.
 
195
 *
 
196
 * For a DirectColor or TrueColor visual, the allocation is determined
 
197
 * by the red_mask, green_mask, and blue_mask members of the visual info.
 
198
 *
 
199
 * Otherwise, if the colormap size is an integral power of 2, determine
 
200
 * the allocation according to the number of bits given to each color,
 
201
 * with green getting more than red, and red more than blue, if there
 
202
 * are to be inequities in the distribution.  If the colormap size is
 
203
 * not an integral power of 2, let n = the number of colormap entries.
 
204
 * Then maximum red value = floor(cube_root(n)) - 1;
 
205
 *      maximum blue value = floor(cube_root(n)) - 1;
 
206
 *      maximum green value = n / ((# red values) * (# blue values)) - 1;
 
207
 * Which, on a GPX, allows for 252 entries in the best map, out of 254
 
208
 * defineable colormap entries.
 
209
 */
 
210
 
 
211
static void
 
212
best_allocation(XVisualInfo *vinfo, unsigned long *red, unsigned long *green,
 
213
                unsigned long *blue)
 
214
{
 
215
 
 
216
    if (vinfo->class == DirectColor ||  vinfo->class == TrueColor)
 
217
    {
 
218
        *red = vinfo->red_mask;
 
219
        while ((*red & 01) == 0)
 
220
            *red >>= 1;
 
221
        *green = vinfo->green_mask;
 
222
        while ((*green & 01) == 0)
 
223
            *green >>=1;
 
224
        *blue = vinfo->blue_mask;
 
225
        while ((*blue & 01) == 0)
 
226
            *blue >>= 1;
 
227
    }
 
228
    else
 
229
    {
 
230
        register int bits, n;
 
231
        
 
232
        /* Determine n such that n is the least integral power of 2 which is
 
233
         * greater than or equal to the number of entries in the colormap.
 
234
         */
 
235
        n = 1;
 
236
        bits = 0;
 
237
        while (vinfo->colormap_size > n)
 
238
        {
 
239
            n = n << 1;
 
240
            bits++;
 
241
        }
 
242
        
 
243
        /* If the number of entries in the colormap is a power of 2, determine
 
244
         * the allocation by "dealing" the bits, first to green, then red, then
 
245
         * blue.  If not, find the maximum integral red, green, and blue values
 
246
         * which, when multiplied together, do not exceed the number of 
 
247
 
 
248
         * colormap entries.
 
249
         */
 
250
        if (n == vinfo->colormap_size)
 
251
        {
 
252
            register int r, g, b;
 
253
            b = bits / 3;
 
254
            g = b + ((bits % 3) ? 1 : 0);
 
255
            r = b + (((bits % 3) == 2) ? 1 : 0);
 
256
            *red = 1 << r;
 
257
            *green = 1 << g;
 
258
            *blue = 1 << b;
 
259
        }
 
260
        else
 
261
        {
 
262
            *red = icbrt_with_bits(vinfo->colormap_size, bits);
 
263
            *blue = *red;       
 
264
            *green = (vinfo->colormap_size / ((*red) * (*blue)));
 
265
        }
 
266
        (*red)--;
 
267
        (*green)--;
 
268
        (*blue)--;
 
269
    }
 
270
    return;
 
271
}
 
272
 
 
273
/*
 
274
 * integer cube roots by Newton's method
 
275
 *
 
276
 * Stephen Gildea, MIT X Consortium, July 1991
 
277
 */
 
278
 
 
279
static int
 
280
icbrt(int a)
 
281
{
 
282
    register int bits = 0;
 
283
    register unsigned n = a;
 
284
 
 
285
    while (n)
 
286
    {
 
287
        bits++;
 
288
        n >>= 1;
 
289
    }
 
290
    return icbrt_with_bits(a, bits);
 
291
}
 
292
 
 
293
 
 
294
static int
 
295
icbrt_with_bits(int a, int bits)
 
296
     /* bits - log 2 of a */
 
297
{
 
298
    return icbrt_with_guess(a, a>>2*bits/3);
 
299
}
 
300
 
 
301
#ifdef _X_ROOT_STATS
 
302
int icbrt_loopcount;
 
303
#endif
 
304
 
 
305
/* Newton's Method:  x_n+1 = x_n - ( f(x_n) / f'(x_n) ) */
 
306
 
 
307
/* for cube roots, x^3 - a = 0,  x_new = x - 1/3 (x - a/x^2) */
 
308
 
 
309
/*
 
310
 * Quick and dirty cube roots.  Nothing fancy here, just Newton's method.
 
311
 * Only works for positive integers (since that's all we need).
 
312
 * We actually return floor(cbrt(a)) because that's what we need here, too.
 
313
 */
 
314
 
 
315
static int
 
316
icbrt_with_guess(int a, int guess)
 
317
{
 
318
    register int delta;
 
319
 
 
320
#ifdef _X_ROOT_STATS
 
321
    icbrt_loopcount = 0;
 
322
#endif
 
323
    if (a <= 0)
 
324
        return 0;
 
325
    if (guess < 1)
 
326
        guess = 1;
 
327
 
 
328
    do {
 
329
#ifdef _X_ROOT_STATS
 
330
        icbrt_loopcount++;
 
331
#endif
 
332
        delta = (guess - a/(guess*guess))/3;
 
333
#ifdef DEBUG
 
334
        printf("pass %d: guess=%d, delta=%d\n", icbrt_loopcount, guess, delta);
 
335
#endif
 
336
        guess -= delta;
 
337
    } while (delta != 0);
 
338
 
 
339
    if (guess*guess*guess > a)
 
340
        guess--;
 
341
 
 
342
    return guess;
 
343
}