server/server/dynbuf.C

/*
 * This file is part of Crossfire TRT, the Roguelike Realtime MORPG.
 * 
 * Copyright (©) 2005,2006,2007 Marc Alexander Lehmann / Robin Redeker / the Crossfire TRT team
 * 
 * Crossfire TRT 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 3 of the License, or
 * (at your option) any later version.
 * 
 * This program 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 program. If not, see <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <crossfire@schmorp.de>
 */

#include "global.h"

#include <cstdio>

dynbuf::dynbuf (int initial, int extend)
{
  ext = extend;
  _size = 0;

  first = last = (chunk *)salloc<char> (sizeof (chunk) + initial);
  first->alloc = sizeof (chunk) + initial;
  first->next = 0;

  ptr = first->data;
  end = ptr + initial;
}

dynbuf::~dynbuf ()
{
  _clear ();
}

void
dynbuf::_clear ()
{
  while (first)
    {
      chunk *next = first->next;

      sfree<char> ((char *)first, first->alloc);
      first = next;
    }
}

void
dynbuf::clear ()
{
  _clear ();
  _size = 0;

  first = last = (chunk *)salloc<char> (sizeof (chunk) + ext);
  first->alloc = sizeof (chunk) + ext;
  first->next = 0;

  ptr = first->data;
  end = ptr + ext;
}

void
dynbuf::finish ()
{
  // finalise current chunk
  _size += last->size = ptr - last->data;
}

void
dynbuf::_reserve (int size)
{
  finish ();

  do
    {
      ext += ext >> 1;
      ext = (ext + 15) & ~15;
    }
  while (ext < size);

  chunk *add = (chunk *) salloc<char> (sizeof (chunk) + ext);
  add->alloc = sizeof (chunk) + ext;
  add->next = 0;

  last->next = add;
  last = add;

  ptr = last->data;
  end = ptr + ext;
}

void
dynbuf::linearise (void *data)
{
  last->size = ptr - last->data;

  for (chunk *c = first; c; c = c->next)
    {
      memcpy (data, c->data, c->size);
      data = (void *)(((char *)data) + c->size);
    }
}

char *
dynbuf::linearise ()
{
  if (first->next)
    {
      finish ();

      chunk *add = (chunk *) salloc<char> (sizeof (chunk) + _size);
      add->alloc = sizeof (chunk) + _size;
      add->next = 0;

      linearise ((void *)add->data);
      _clear ();

      first = last = add;
      ptr = last->data + _size;
      end = ptr;
      _size = 0;
    }

  return first->data;
}

dynbuf::operator std::string ()
{
  // could optimise
  return std::string (linearise (), size ());
}

void
dynbuf_text::printf (const char *format, ...)
{
  int len;

  {
    force (128);

    va_list ap;
    va_start (ap, format);
    len = vsnprintf (ptr, end - ptr, format, ap);
    va_end (ap);

    assert (len >= 0); // shield against broken vsnprintf's

    // was enough room available
    if (ptr + len < end)
      {
        ptr += len;
        return;
      }
  }

  // longer, try harder
  va_list ap;
  va_start (ap, format);
  vsnprintf (force (len + 1), len + 1, format, ap);
  va_end (ap);

  ptr += len;
}

// simply return a mask with "bits" bits set
inline uint64
m (int b)
{
  return (uint64 (1) << b) - 1;
}

// convert 9 digits to ascii, using only a single multiplication
// (depending on cpu and compiler).
// will generate a single 0 as output when v=lz=0
inline char *
i2a_9 (char *ptr, uint32 v, bool lz)
{
  // convert to 4.56 fixed-point representation
  // this should be optimal on 64 bit cpus, and rather
  // slow on 32 bit cpus. go figure :)
  const int bits = 7*8; // 7 bits per post-comma digit

  uint64 u = v * ((m (bits) + 100000000) / 100000000); // 10**8

  if (lz)
    {
      // output leading zeros
      // good compilers will compile this into only shifts, masks and adds
      *ptr++ = char (u >> (bits - 0)) + '0'; u = (u & m (bits - 0)) * 5;
      *ptr++ = char (u >> (bits - 1)) + '0'; u = (u & m (bits - 1)) * 5;
      *ptr++ = char (u >> (bits - 2)) + '0'; u = (u & m (bits - 2)) * 5;
      *ptr++ = char (u >> (bits - 3)) + '0'; u = (u & m (bits - 3)) * 5;
      *ptr++ = char (u >> (bits - 4)) + '0'; u = (u & m (bits - 4)) * 5;
      *ptr++ = char (u >> (bits - 5)) + '0'; u = (u & m (bits - 5)) * 5;
      *ptr++ = char (u >> (bits - 6)) + '0'; u = (u & m (bits - 6)) * 5;
      *ptr++ = char (u >> (bits - 7)) + '0'; u = (u & m (bits - 7)) * 5;
      *ptr++ = char (u >> (bits - 8)) + '0';
    }
  else
    {
      // do not output leading zeroes (except if v == 0)
      // good compilers will compile this into completely branchless code
      char digit, nz = 0;

      digit = (u >> (bits - 0)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 0)) * 5;
      digit = (u >> (bits - 1)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 1)) * 5;
      digit = (u >> (bits - 2)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 2)) * 5;
      digit = (u >> (bits - 3)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 3)) * 5;
      digit = (u >> (bits - 4)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 4)) * 5;
      digit = (u >> (bits - 5)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 5)) * 5;
      digit = (u >> (bits - 6)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 6)) * 5;
      digit = (u >> (bits - 7)); *ptr = digit + '0'; nz |= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 7)) * 5;
      digit = (u >> (bits - 8)); *ptr = digit + '0'; nz |= digit; ptr += 1;
    }

  return ptr;
}

void
dynbuf_text::add (sint32 i)
{
  force (sint32_digits);

  *ptr = '-'; ptr += i < 0 ? 1 : 0;
  uint32 u = i < 0 ? -i : i;

  if (expect_true (u < 10)) // we have a lot of single-digit numbers, so optimise
    fadd (char (u + '0'));
  else if (expect_true (u < 1000000000)) // 9 0's
    ptr = i2a_9 (ptr, u, false);
  else
    {
      sint32 div = u / 1000000000;
      uint32 rem = u % 1000000000;

      ptr = i2a_9 (ptr, div, false);
      ptr = i2a_9 (ptr, rem, true);
    }
}

void
dynbuf_text::add (sint64 i)
{
  force (sint64_digits);

  *ptr = '-'; ptr += i < 0 ? 1 : 0;
  uint64 u = i < 0 ? -i : i;

  // split the number into a 1-digit part
  // (#19) and two 9 digit parts (9..18 and 0..8)

  // good compilers will only use multiplications here

  if (u < 10) // we have a lot of single-digit numbers, so optimise
    fadd (char (u + '0'));
  else if (expect_true (u < 1000000000)) // 9 0's
    ptr = i2a_9 (ptr, u, false);
  else if (expect_true (u < UINT64_C (1000000000000000000))) // 18 0's
    {
      sint32 div = u / 1000000000;
      uint32 rem = u % 1000000000;

      ptr = i2a_9 (ptr, div, false);
      ptr = i2a_9 (ptr, rem, true);
    }
  else
    {
      // a biggy
      sint32 div = u / UINT64_C (1000000000000000000);
      uint64 rem = u % UINT64_C (1000000000000000000);

      fadd (char (div + '0'));
      u = rem;

      {
        sint32 div = u / 1000000000;
        uint32 rem = u % 1000000000;

        ptr = i2a_9 (ptr, div, true);
        ptr = i2a_9 (ptr, rem, true);
      }
    }
}

#if 0
struct dynbuf_test_class {
  dynbuf_test_class ()
  {
    sint64 s = 0;
    for (int i = 0; i < 10000000; ++i)
      {
        char b1[256], b2[256];

        dynbuf_text db;
        db.add (s);
        db.add (char (0));

        db.linearise (b1);
        sprintf (b2, "%ld", s);

        if (strcmp (b1, b2))
          printf ("<%s,%s>\n", b1, b2);

        if (i < 20)
          s = (sint64) pow (10., i);
        else
          s = (sint64) exp (random () * (43.6682723752766 / RAND_MAX));
      }

    exit (0);
  }
} dynbuf_test;
#endif
Revision:	1.16
Committed:	Sun Jul 1 05:00:20 2007 UTC (16 years, 11 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.15:	+10 -11 lines
Log Message:	- upgrade crossfire trt to the GPL version 3 (hopefully correctly). - add a single file covered by the GNU Affero General Public License (which is not yet released, so I used the current draft, which is legally a bit wavy, but its likely better than nothing as it expresses direct intent by the authors, and we can upgrade as soon as it has been released). * this should ensure availability of source code for the server at least and hopefully also archetypes and maps even when modified versions are not being distributed, in accordance of section 13 of the agplv3.
#	Content
1	/*
2	* This file is part of Crossfire TRT, the Roguelike Realtime MORPG.
3	*
4	* Copyright (©) 2005,2006,2007 Marc Alexander Lehmann / Robin Redeker / the Crossfire TRT team
5	*
6	* Crossfire TRT is free software: you can redistribute it and/or modify
7	* it under the terms of the GNU General Public License as published by
8	* the Free Software Foundation, either version 3 of the License, or
9	* (at your option) any later version.
10	*
11	* This program is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU General Public License for more details.
15	*
16	* You should have received a copy of the GNU General Public License
17	* along with this program. If not, see <http://www.gnu.org/licenses/>.
18	*
19	* The authors can be reached via e-mail to <crossfire@schmorp.de>
20	*/
21
22	#include "global.h"
23
24	#include <cstdio>
25
26	dynbuf::dynbuf (int initial, int extend)
27	{
28	ext = extend;
29	_size = 0;
30
31	first = last = (chunk *)salloc<char> (sizeof (chunk) + initial);
32	first->alloc = sizeof (chunk) + initial;
33	first->next = 0;
34
35	ptr = first->data;
36	end = ptr + initial;
37	}
38
39	dynbuf::~dynbuf ()
40	{
41	_clear ();
42	}
43
44	void
45	dynbuf::_clear ()
46	{
47	while (first)
48	{
49	chunk *next = first->next;
50
51	sfree<char> ((char *)first, first->alloc);
52	first = next;
53	}
54	}
55
56	void
57	dynbuf::clear ()
58	{
59	_clear ();
60	_size = 0;
61
62	first = last = (chunk *)salloc<char> (sizeof (chunk) + ext);
63	first->alloc = sizeof (chunk) + ext;
64	first->next = 0;
65
66	ptr = first->data;
67	end = ptr + ext;
68	}
69
70	void
71	dynbuf::finish ()
72	{
73	// finalise current chunk
74	_size += last->size = ptr - last->data;
75	}
76
77	void
78	dynbuf::_reserve (int size)
79	{
80	finish ();
81
82	do
83	{
84	ext += ext >> 1;
85	ext = (ext + 15) & ~15;
86	}
87	while (ext < size);
88
89	chunk add = (chunk ) salloc<char> (sizeof (chunk) + ext);
90	add->alloc = sizeof (chunk) + ext;
91	add->next = 0;
92
93	last->next = add;
94	last = add;
95
96	ptr = last->data;
97	end = ptr + ext;
98	}
99
100	void
101	dynbuf::linearise (void *data)
102	{
103	last->size = ptr - last->data;
104
105	for (chunk *c = first; c; c = c->next)
106	{
107	memcpy (data, c->data, c->size);
108	data = (void )(((char )data) + c->size);
109	}
110	}
111
112	char *
113	dynbuf::linearise ()
114	{
115	if (first->next)
116	{
117	finish ();
118
119	chunk add = (chunk ) salloc<char> (sizeof (chunk) + _size);
120	add->alloc = sizeof (chunk) + _size;
121	add->next = 0;
122
123	linearise ((void *)add->data);
124	_clear ();
125
126	first = last = add;
127	ptr = last->data + _size;
128	end = ptr;
129	_size = 0;
130	}
131
132	return first->data;
133	}
134
135	dynbuf::operator std::string ()
136	{
137	// could optimise
138	return std::string (linearise (), size ());
139	}
140
141	void
142	dynbuf_text::printf (const char *format, ...)
143	{
144	int len;
145
146	{
147	force (128);
148
149	va_list ap;
150	va_start (ap, format);
151	len = vsnprintf (ptr, end - ptr, format, ap);
152	va_end (ap);
153
154	assert (len >= 0); // shield against broken vsnprintf's
155
156	// was enough room available
157	if (ptr + len < end)
158	{
159	ptr += len;
160	return;
161	}
162	}
163
164	// longer, try harder
165	va_list ap;
166	va_start (ap, format);
167	vsnprintf (force (len + 1), len + 1, format, ap);
168	va_end (ap);
169
170	ptr += len;
171	}
172
173	// simply return a mask with "bits" bits set
174	inline uint64
175	m (int b)
176	{
177	return (uint64 (1) << b) - 1;
178	}
179
180	// convert 9 digits to ascii, using only a single multiplication
181	// (depending on cpu and compiler).
182	// will generate a single 0 as output when v=lz=0
183	inline char *
184	i2a_9 (char *ptr, uint32 v, bool lz)
185	{
186	// convert to 4.56 fixed-point representation
187	// this should be optimal on 64 bit cpus, and rather
188	// slow on 32 bit cpus. go figure :)
189	const int bits = 7*8; // 7 bits per post-comma digit
190
191	uint64 u = v * ((m (bits) + 100000000) / 100000000); // 10**8
192
193	if (lz)
194	{
195	// output leading zeros
196	// good compilers will compile this into only shifts, masks and adds
197	ptr++ = char (u >> (bits - 0)) + '0'; u = (u & m (bits - 0)) 5;
198	ptr++ = char (u >> (bits - 1)) + '0'; u = (u & m (bits - 1)) 5;
199	ptr++ = char (u >> (bits - 2)) + '0'; u = (u & m (bits - 2)) 5;
200	ptr++ = char (u >> (bits - 3)) + '0'; u = (u & m (bits - 3)) 5;
201	ptr++ = char (u >> (bits - 4)) + '0'; u = (u & m (bits - 4)) 5;
202	ptr++ = char (u >> (bits - 5)) + '0'; u = (u & m (bits - 5)) 5;
203	ptr++ = char (u >> (bits - 6)) + '0'; u = (u & m (bits - 6)) 5;
204	ptr++ = char (u >> (bits - 7)) + '0'; u = (u & m (bits - 7)) 5;
205	*ptr++ = char (u >> (bits - 8)) + '0';
206	}
207	else
208	{
209	// do not output leading zeroes (except if v == 0)
210	// good compilers will compile this into completely branchless code
211	char digit, nz = 0;
212
213	digit = (u >> (bits - 0)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 0)) 5;
214	digit = (u >> (bits - 1)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 1)) 5;
215	digit = (u >> (bits - 2)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 2)) 5;
216	digit = (u >> (bits - 3)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 3)) 5;
217	digit = (u >> (bits - 4)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 4)) 5;
218	digit = (u >> (bits - 5)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 5)) 5;
219	digit = (u >> (bits - 6)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 6)) 5;
220	digit = (u >> (bits - 7)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 7)) 5;
221	digit = (u >> (bits - 8)); *ptr = digit + '0'; nz \|= digit; ptr += 1;
222	}
223
224	return ptr;
225	}
226
227	void
228	dynbuf_text::add (sint32 i)
229	{
230	force (sint32_digits);
231
232	*ptr = '-'; ptr += i < 0 ? 1 : 0;
233	uint32 u = i < 0 ? -i : i;
234
235	if (expect_true (u < 10)) // we have a lot of single-digit numbers, so optimise
236	fadd (char (u + '0'));
237	else if (expect_true (u < 1000000000)) // 9 0's
238	ptr = i2a_9 (ptr, u, false);
239	else
240	{
241	sint32 div = u / 1000000000;
242	uint32 rem = u % 1000000000;
243
244	ptr = i2a_9 (ptr, div, false);
245	ptr = i2a_9 (ptr, rem, true);
246	}
247	}
248
249	void
250	dynbuf_text::add (sint64 i)
251	{
252	force (sint64_digits);
253
254	*ptr = '-'; ptr += i < 0 ? 1 : 0;
255	uint64 u = i < 0 ? -i : i;
256
257	// split the number into a 1-digit part
258	// (#19) and two 9 digit parts (9..18 and 0..8)
259
260	// good compilers will only use multiplications here
261
262	if (u < 10) // we have a lot of single-digit numbers, so optimise
263	fadd (char (u + '0'));
264	else if (expect_true (u < 1000000000)) // 9 0's
265	ptr = i2a_9 (ptr, u, false);
266	else if (expect_true (u < UINT64_C (1000000000000000000))) // 18 0's
267	{
268	sint32 div = u / 1000000000;
269	uint32 rem = u % 1000000000;
270
271	ptr = i2a_9 (ptr, div, false);
272	ptr = i2a_9 (ptr, rem, true);
273	}
274	else
275	{
276	// a biggy
277	sint32 div = u / UINT64_C (1000000000000000000);
278	uint64 rem = u % UINT64_C (1000000000000000000);
279
280	fadd (char (div + '0'));
281	u = rem;
282
283	{
284	sint32 div = u / 1000000000;
285	uint32 rem = u % 1000000000;
286
287	ptr = i2a_9 (ptr, div, true);
288	ptr = i2a_9 (ptr, rem, true);
289	}
290	}
291	}
292
293	#if 0
294	struct dynbuf_test_class {
295	dynbuf_test_class ()
296	{
297	sint64 s = 0;
298	for (int i = 0; i < 10000000; ++i)
299	{
300	char b1[256], b2[256];
301
302	dynbuf_text db;
303	db.add (s);
304	db.add (char (0));
305
306	db.linearise (b1);
307	sprintf (b2, "%ld", s);
308
309	if (strcmp (b1, b2))
310	printf ("<%s,%s>\n", b1, b2);
311
312	if (i < 20)
313	s = (sint64) pow (10., i);
314	else
315	s = (sint64) exp (random () * (43.6682723752766 / RAND_MAX));
316	}
317
318	exit (0);
319	}
320	} dynbuf_test;
321	#endif