1 | /* |
2 | * QEMU VNC display driver: palette hash table |
3 | * |
4 | * From libvncserver/libvncserver/tight.c |
5 | * Copyright (C) 2000, 2001 Const Kaplinsky. All Rights Reserved. |
6 | * Copyright (C) 1999 AT&T Laboratories Cambridge. All Rights Reserved. |
7 | * |
8 | * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> |
9 | * |
10 | * Permission is hereby granted, free of charge, to any person obtaining a copy |
11 | * of this software and associated documentation files (the "Software"), to deal |
12 | * in the Software without restriction, including without limitation the rights |
13 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
14 | * copies of the Software, and to permit persons to whom the Software is |
15 | * furnished to do so, subject to the following conditions: |
16 | * |
17 | * The above copyright notice and this permission notice shall be included in |
18 | * all copies or substantial portions of the Software. |
19 | * |
20 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
21 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
23 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
24 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
25 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
26 | * THE SOFTWARE. |
27 | */ |
28 | |
29 | #include "qemu/osdep.h" |
30 | #include "vnc-palette.h" |
31 | |
32 | static VncPaletteEntry *palette_find(const VncPalette *palette, |
33 | uint32_t color, unsigned int hash) |
34 | { |
35 | VncPaletteEntry *entry; |
36 | |
37 | QLIST_FOREACH(entry, &palette->table[hash], next) { |
38 | if (entry->color == color) { |
39 | return entry; |
40 | } |
41 | } |
42 | |
43 | return NULL; |
44 | } |
45 | |
46 | static unsigned int palette_hash(uint32_t rgb, int bpp) |
47 | { |
48 | if (bpp == 16) { |
49 | return ((unsigned int)(((rgb >> 8) + rgb) & 0xFF)); |
50 | } else { |
51 | return ((unsigned int)(((rgb >> 16) + (rgb >> 8)) & 0xFF)); |
52 | } |
53 | } |
54 | |
55 | VncPalette *palette_new(size_t max, int bpp) |
56 | { |
57 | VncPalette *palette; |
58 | |
59 | palette = g_malloc0(sizeof(*palette)); |
60 | palette_init(palette, max, bpp); |
61 | return palette; |
62 | } |
63 | |
64 | void palette_init(VncPalette *palette, size_t max, int bpp) |
65 | { |
66 | memset(palette, 0, sizeof (*palette)); |
67 | palette->max = max; |
68 | palette->bpp = bpp; |
69 | } |
70 | |
71 | void palette_destroy(VncPalette *palette) |
72 | { |
73 | g_free(palette); |
74 | } |
75 | |
76 | int palette_put(VncPalette *palette, uint32_t color) |
77 | { |
78 | unsigned int hash; |
79 | unsigned int idx = palette->size; |
80 | VncPaletteEntry *entry; |
81 | |
82 | hash = palette_hash(color, palette->bpp) % VNC_PALETTE_HASH_SIZE; |
83 | entry = palette_find(palette, color, hash); |
84 | |
85 | if (!entry && palette->size >= palette->max) { |
86 | return 0; |
87 | } |
88 | if (!entry) { |
89 | VncPaletteEntry *entry; |
90 | |
91 | entry = &palette->pool[palette->size]; |
92 | entry->color = color; |
93 | entry->idx = idx; |
94 | QLIST_INSERT_HEAD(&palette->table[hash], entry, next); |
95 | palette->size++; |
96 | } |
97 | return palette->size; |
98 | } |
99 | |
100 | int palette_idx(const VncPalette *palette, uint32_t color) |
101 | { |
102 | VncPaletteEntry *entry; |
103 | unsigned int hash; |
104 | |
105 | hash = palette_hash(color, palette->bpp) % VNC_PALETTE_HASH_SIZE; |
106 | entry = palette_find(palette, color, hash); |
107 | return (entry == NULL ? -1 : entry->idx); |
108 | } |
109 | |
110 | size_t palette_size(const VncPalette *palette) |
111 | { |
112 | return palette->size; |
113 | } |
114 | |
115 | void palette_iter(const VncPalette *palette, |
116 | void (*iter)(int idx, uint32_t color, void *opaque), |
117 | void *opaque) |
118 | { |
119 | int i; |
120 | VncPaletteEntry *entry; |
121 | |
122 | for (i = 0; i < VNC_PALETTE_HASH_SIZE; i++) { |
123 | QLIST_FOREACH(entry, &palette->table[i], next) { |
124 | iter(entry->idx, entry->color, opaque); |
125 | } |
126 | } |
127 | } |
128 | |
129 | uint32_t palette_color(const VncPalette *palette, int idx, bool *found) |
130 | { |
131 | int i; |
132 | VncPaletteEntry *entry; |
133 | |
134 | for (i = 0; i < VNC_PALETTE_HASH_SIZE; i++) { |
135 | QLIST_FOREACH(entry, &palette->table[i], next) { |
136 | if (entry->idx == idx) { |
137 | *found = true; |
138 | return entry->color; |
139 | } |
140 | } |
141 | } |
142 | |
143 | *found = false; |
144 | return -1; |
145 | } |
146 | |
147 | static void palette_fill_cb(int idx, uint32_t color, void *opaque) |
148 | { |
149 | uint32_t *colors = opaque; |
150 | |
151 | colors[idx] = color; |
152 | } |
153 | |
154 | size_t palette_fill(const VncPalette *palette, |
155 | uint32_t colors[VNC_PALETTE_MAX_SIZE]) |
156 | { |
157 | palette_iter(palette, palette_fill_cb, colors); |
158 | return palette_size(palette); |
159 | } |
160 | |