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