1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
/* Copyright (C) 2000-2005 Constantin Kaplinsky. All Rights Reserved.
* Copyright (C) 2011 D. R. Commander. All Rights Reserved.
* Copyright 2014 Pierre Ossman for Cendio AB
*
* This is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This software is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this software; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
* USA.
*/
#ifndef __RFB_PALETTE_H__
#define __RFB_PALETTE_H__
#include <assert.h>
#include <string.h>
#include <rdr/types.h>
namespace rfb {
class Palette {
public:
Palette() { clear(); }
~Palette() {}
int size() const { return numColours; }
void clear() { numColours = 0; memset(hash, 0, sizeof(hash)); }
inline bool insert(rdr::U32 colour, int numPixels);
inline unsigned char lookup(rdr::U32 colour) const;
inline rdr::U32 getColour(unsigned char index) const;
inline int getCount(unsigned char index) const;
protected:
inline unsigned char genHash(rdr::U32 colour) const;
protected:
int numColours;
struct PaletteListNode {
PaletteListNode *next;
unsigned char idx;
rdr::U32 colour;
};
struct PaletteEntry {
PaletteListNode *listNode;
int numPixels;
};
// This is the raw list of colours, allocated from 0 and up
PaletteListNode list[256];
// Hash table for quick lookup into the list above
PaletteListNode *hash[256];
// Occurances of each colour, where the 0:th entry is the most common.
// Indices also refer to this array.
PaletteEntry entry[256];
};
}
inline bool rfb::Palette::insert(rdr::U32 colour, int numPixels)
{
PaletteListNode* pnode;
PaletteListNode* prev_pnode;
unsigned char hash_key, idx;
hash_key = genHash(colour);
pnode = hash[hash_key];
prev_pnode = NULL;
// Do we already have an entry for this colour?
while (pnode != NULL) {
if (pnode->colour == colour) {
// Yup
idx = pnode->idx;
numPixels = entry[idx].numPixels + numPixels;
// The extra pixels might mean we have to adjust the sort list
while (idx > 0) {
if (entry[idx-1].numPixels >= numPixels)
break;
entry[idx] = entry[idx-1];
entry[idx].listNode->idx = idx;
idx--;
}
if (idx != pnode->idx) {
entry[idx].listNode = pnode;
pnode->idx = idx;
}
entry[idx].numPixels = numPixels;
return true;
}
prev_pnode = pnode;
pnode = pnode->next;
}
// Check if palette is full.
if (numColours == 256)
return false;
// Create a new colour entry
pnode = &list[numColours];
pnode->next = NULL;
pnode->idx = 0;
pnode->colour = colour;
// Add it to the hash table
if (prev_pnode != NULL)
prev_pnode->next = pnode;
else
hash[hash_key] = pnode;
// Move palette entries with lesser pixel counts.
idx = numColours;
while (idx > 0) {
if (entry[idx-1].numPixels >= numPixels)
break;
entry[idx] = entry[idx-1];
entry[idx].listNode->idx = idx;
idx--;
}
// And add it into the freed slot.
pnode->idx = idx;
entry[idx].listNode = pnode;
entry[idx].numPixels = numPixels;
numColours++;
return true;
}
inline unsigned char rfb::Palette::lookup(rdr::U32 colour) const
{
unsigned char hash_key;
PaletteListNode* pnode;
hash_key = genHash(colour);
pnode = hash[hash_key];
while (pnode != NULL) {
if (pnode->colour == colour)
return pnode->idx;
pnode = pnode->next;
}
// We are being fed a bad colour
assert(false);
return 0;
}
inline rdr::U32 rfb::Palette::getColour(unsigned char index) const
{
return entry[index].listNode->colour;
}
inline int rfb::Palette::getCount(unsigned char index) const
{
return entry[index].numPixels;
}
inline unsigned char rfb::Palette::genHash(rdr::U32 colour) const
{
unsigned char hash_key;
// djb2 hash function
hash_key = 5; // 5381 & 0xff
for (int i = 0; i < 32; i += 8)
hash_key = ((hash_key << 5) + hash_key) ^ (colour >> i);
return hash_key;
}
#endif
|
