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.
#	User	Rev	Content
1	root	1.15	/*
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	root	1.16	* 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	root	1.15	*
11	root	1.16	* 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	root	1.15	*
16	root	1.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	root	1.15	*
19			* The authors can be reached via e-mail to <crossfire@schmorp.de>
20			*/
21
22	root	1.1	#include "global.h"
23
24			#include <cstdio>
25
26			dynbuf::dynbuf (int initial, int extend)
27			{
28	root	1.10	ext = extend;
29	root	1.1	_size = 0;
30	root	1.5
31	root	1.8	first = last = (chunk *)salloc<char> (sizeof (chunk) + initial);
32			first->alloc = sizeof (chunk) + initial;
33	root	1.1	first->next = 0;
34	root	1.8
35	root	1.5	ptr = first->data;
36	root	1.9	end = ptr + initial;
37	root	1.1	}
38
39			dynbuf::~dynbuf ()
40			{
41	root	1.10	_clear ();
42	root	1.1	}
43
44	root	1.5	void
45	root	1.10	dynbuf::_clear ()
46	root	1.1	{
47			while (first)
48			{
49			chunk *next = first->next;
50	root	1.5
51	root	1.8	sfree<char> ((char *)first, first->alloc);
52	root	1.1	first = next;
53			}
54	root	1.5	}
55	root	1.1
56	root	1.5	void
57	root	1.10	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	root	1.5	dynbuf::finish ()
72	root	1.1	{
73			// finalise current chunk
74			_size += last->size = ptr - last->data;
75			}
76
77	root	1.5	void
78			dynbuf::_reserve (int size)
79	root	1.1	{
80			finish ();
81
82			do
83			{
84			ext += ext >> 1;
85			ext = (ext + 15) & ~15;
86			}
87			while (ext < size);
88
89	root	1.8	chunk add = (chunk ) salloc<char> (sizeof (chunk) + ext);
90			add->alloc = sizeof (chunk) + ext;
91	root	1.1	add->next = 0;
92
93			last->next = add;
94			last = add;
95
96	root	1.5	ptr = last->data;
97	root	1.9	end = ptr + ext;
98	root	1.1	}
99
100	root	1.5	void
101			dynbuf::linearise (void *data)
102	root	1.1	{
103			last->size = ptr - last->data;
104
105	root	1.10	for (chunk *c = first; c; c = c->next)
106	root	1.1	{
107	root	1.10	memcpy (data, c->data, c->size);
108			data = (void )(((char )data) + c->size);
109	root	1.1	}
110			}
111
112	root	1.5	char *
113			dynbuf::linearise ()
114	root	1.1	{
115			if (first->next)
116			{
117			finish ();
118
119	root	1.8	chunk add = (chunk ) salloc<char> (sizeof (chunk) + _size);
120			add->alloc = sizeof (chunk) + _size;
121			add->next = 0;
122	root	1.1
123	root	1.8	linearise ((void *)add->data);
124	root	1.10	_clear ();
125	root	1.1
126			first = last = add;
127	root	1.5	ptr = last->data + _size;
128	root	1.9	end = ptr;
129	root	1.1	_size = 0;
130			}
131
132			return first->data;
133			}
134
135	root	1.7	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	root	1.9	len = vsnprintf (ptr, end - ptr, format, ap);
152	root	1.7	va_end (ap);
153
154			assert (len >= 0); // shield against broken vsnprintf's
155
156			// was enough room available
157	root	1.9	if (ptr + len < end)
158	root	1.7	{
159	root	1.13	ptr += len;
160	root	1.7	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	root	1.13	ptr += len;
171	root	1.7	}
172
173	root	1.11	// simply return a mask with "bits" bits set
174			inline uint64
175			m (int b)
176	root	1.1	{
177	root	1.11	return (uint64 (1) << b) - 1;
178			}
179	root	1.1
180	root	1.11	// 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	root	1.12	const int bits = 7*8; // 7 bits per post-comma digit
190	root	1.11
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	root	1.1	}
207			else
208	root	1.4	{
209	root	1.11	// 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	root	1.4	}
223	root	1.1
224	root	1.11	return ptr;
225			}
226
227			void
228			dynbuf_text::add (sint32 i)
229			{
230	root	1.14	force (sint32_digits);
231	root	1.11
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	root	1.1	{
241	root	1.11	sint32 div = u / 1000000000;
242			uint32 rem = u % 1000000000;
243	root	1.5
244	root	1.11	ptr = i2a_9 (ptr, div, false);
245			ptr = i2a_9 (ptr, rem, true);
246	root	1.1	}
247			}
248
249	root	1.5	void
250	root	1.7	dynbuf_text::add (sint64 i)
251	root	1.1	{
252	root	1.14	force (sint64_digits);
253	root	1.11
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	root	1.4
260	root	1.11	// good compilers will only use multiplications here
261	root	1.2
262	root	1.11	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	root	1.1	{
268	root	1.11	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	root	1.1	}
274	root	1.2	else
275	root	1.1	{
276	root	1.11	// 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	root	1.1	}
291	root	1.11	}
292	root	1.1
293	root	1.11	#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