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>

void
dynbuf::init (int initial)
{
  _size = 0;

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

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

void
dynbuf::free (chunk *&chain)
{
  while (chain)
    {
      chunk *next = chain->next;

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

void
dynbuf::clear ()
{
  free (first->next);

  _size = 0;
  ptr = first->data;
  end = ptr + first->alloc - sizeof (chunk);
}

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

void
dynbuf::reserve (int size)
{
  finalise ();

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

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

  last->next = add;
  last = add;

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

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 ()
{
  finalise ();

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

  linearise ((void *)add->data);
  free (first);

  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);
      }
    }
}

dynbuf_text::operator const char *()
{
  *this << '\0';
  linearise ();
  --ptr;
  return first->data;
}

void
dynbuf_text::add_abilities (const char *name, uint32 abilities)
{
  if (!abilities)
    return;

  *this << '(' << name;

  const char *sep = ": ";
  for (int i = 0; i < NROFATTACKS; ++i)
    if (abilities & (1 << i))
      {
        *this << sep; sep = ", ";
        *this << attacks [i];
      }

  *this << ')';
}

void
dynbuf_text::add_paths (const char *name, uint32 paths)
{
  if (!paths)
    return;

  *this << '(' << name;

  const char *sep = ": ";
  for (int i = 0; i < NRSPELLPATHS; ++i)
    if (paths & (1 << i))
      {
        *this << sep; sep = ", ";
        *this << spellpathnames [i];
      }

  *this << ')';
}

#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.17
Committed:	Tue Jul 10 05:51:38 2007 UTC (16 years, 10 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.16:	+79 -44 lines
Log Message:	- improve dynbuf implementation further - save now saves shstrs longer than HUGE_BUF, lets fix any brokenness remaining in the server... - converted most describe_*-functions to dynbuf_text, making them likely faster (or maybe slower), while removing any hardcoded length limit. - memory allocated for static dynbuf's is not being returned ever (at least not the initial chunk, maybe fix this?) - implement framework for predeclared const shstrs for comparison purposes (shstrinc.h). - enabled and enforced new material code. - implement hack to clean up book titles. - increases HUGE_BUF to 10240, to be similar to mac network packet size.
#	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	root	1.17	void
27			dynbuf::init (int initial)
28	root	1.1	{
29			_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	root	1.5	void
40	root	1.17	dynbuf::free (chunk *&chain)
41	root	1.1	{
42	root	1.17	while (chain)
43	root	1.1	{
44	root	1.17	chunk *next = chain->next;
45	root	1.5
46	root	1.17	sfree<char> ((char *)chain, chain->alloc);
47			chain = next;
48	root	1.1	}
49	root	1.5	}
50	root	1.1
51	root	1.5	void
52	root	1.10	dynbuf::clear ()
53			{
54	root	1.17	free (first->next);
55
56	root	1.10	_size = 0;
57			ptr = first->data;
58	root	1.17	end = ptr + first->alloc - sizeof (chunk);
59	root	1.10	}
60
61			void
62	root	1.17	dynbuf::finalise ()
63	root	1.1	{
64			// finalise current chunk
65			_size += last->size = ptr - last->data;
66			}
67
68	root	1.5	void
69	root	1.17	dynbuf::reserve (int size)
70	root	1.1	{
71	root	1.17	finalise ();
72	root	1.1
73			do
74			{
75	root	1.17	extend += extend >> 1;
76			extend = (extend + 15) & ~15;
77	root	1.1	}
78	root	1.17	while (extend < size);
79	root	1.1
80	root	1.17	chunk add = (chunk ) salloc<char> (sizeof (chunk) + extend);
81			add->alloc = sizeof (chunk) + extend;
82	root	1.1	add->next = 0;
83
84			last->next = add;
85			last = add;
86
87	root	1.5	ptr = last->data;
88	root	1.17	end = ptr + extend;
89	root	1.1	}
90
91	root	1.5	void
92			dynbuf::linearise (void *data)
93	root	1.1	{
94			last->size = ptr - last->data;
95
96	root	1.10	for (chunk *c = first; c; c = c->next)
97	root	1.1	{
98	root	1.10	memcpy (data, c->data, c->size);
99			data = (void )(((char )data) + c->size);
100	root	1.1	}
101			}
102
103	root	1.5	char *
104	root	1.17	dynbuf::_linearise ()
105	root	1.1	{
106	root	1.17	finalise ();
107
108			chunk add = (chunk ) salloc<char> (sizeof (chunk) + _size);
109			add->alloc = sizeof (chunk) + _size;
110			add->next = 0;
111
112			linearise ((void *)add->data);
113			free (first);
114	root	1.1
115	root	1.17	first = last = add;
116			ptr = last->data + _size;
117			end = ptr;
118			_size = 0;
119	root	1.1
120			return first->data;
121			}
122
123	root	1.7	dynbuf::operator std::string ()
124			{
125			// could optimise
126			return std::string (linearise (), size ());
127			}
128
129			void
130			dynbuf_text::printf (const char *format, ...)
131			{
132			int len;
133
134			{
135			force (128);
136
137			va_list ap;
138			va_start (ap, format);
139	root	1.9	len = vsnprintf (ptr, end - ptr, format, ap);
140	root	1.7	va_end (ap);
141
142			assert (len >= 0); // shield against broken vsnprintf's
143
144			// was enough room available
145	root	1.9	if (ptr + len < end)
146	root	1.7	{
147	root	1.13	ptr += len;
148	root	1.7	return;
149			}
150			}
151
152			// longer, try harder
153			va_list ap;
154			va_start (ap, format);
155			vsnprintf (force (len + 1), len + 1, format, ap);
156			va_end (ap);
157
158	root	1.13	ptr += len;
159	root	1.7	}
160
161	root	1.11	// simply return a mask with "bits" bits set
162			inline uint64
163			m (int b)
164	root	1.1	{
165	root	1.11	return (uint64 (1) << b) - 1;
166			}
167	root	1.1
168	root	1.11	// convert 9 digits to ascii, using only a single multiplication
169			// (depending on cpu and compiler).
170			// will generate a single 0 as output when v=lz=0
171			inline char *
172			i2a_9 (char *ptr, uint32 v, bool lz)
173			{
174			// convert to 4.56 fixed-point representation
175			// this should be optimal on 64 bit cpus, and rather
176			// slow on 32 bit cpus. go figure :)
177	root	1.12	const int bits = 7*8; // 7 bits per post-comma digit
178	root	1.11
179			uint64 u = v * ((m (bits) + 100000000) / 100000000); // 10**8
180
181			if (lz)
182			{
183			// output leading zeros
184			// good compilers will compile this into only shifts, masks and adds
185			ptr++ = char (u >> (bits - 0)) + '0'; u = (u & m (bits - 0)) 5;
186			ptr++ = char (u >> (bits - 1)) + '0'; u = (u & m (bits - 1)) 5;
187			ptr++ = char (u >> (bits - 2)) + '0'; u = (u & m (bits - 2)) 5;
188			ptr++ = char (u >> (bits - 3)) + '0'; u = (u & m (bits - 3)) 5;
189			ptr++ = char (u >> (bits - 4)) + '0'; u = (u & m (bits - 4)) 5;
190			ptr++ = char (u >> (bits - 5)) + '0'; u = (u & m (bits - 5)) 5;
191			ptr++ = char (u >> (bits - 6)) + '0'; u = (u & m (bits - 6)) 5;
192			ptr++ = char (u >> (bits - 7)) + '0'; u = (u & m (bits - 7)) 5;
193			*ptr++ = char (u >> (bits - 8)) + '0';
194	root	1.1	}
195			else
196	root	1.4	{
197	root	1.11	// do not output leading zeroes (except if v == 0)
198			// good compilers will compile this into completely branchless code
199			char digit, nz = 0;
200
201			digit = (u >> (bits - 0)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 0)) 5;
202			digit = (u >> (bits - 1)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 1)) 5;
203			digit = (u >> (bits - 2)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 2)) 5;
204			digit = (u >> (bits - 3)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 3)) 5;
205			digit = (u >> (bits - 4)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 4)) 5;
206			digit = (u >> (bits - 5)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 5)) 5;
207			digit = (u >> (bits - 6)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 6)) 5;
208			digit = (u >> (bits - 7)); ptr = digit + '0'; nz \|= digit; ptr += nz ? 1 : 0; u = (u & m (bits - 7)) 5;
209			digit = (u >> (bits - 8)); *ptr = digit + '0'; nz \|= digit; ptr += 1;
210	root	1.4	}
211	root	1.1
212	root	1.11	return ptr;
213			}
214
215			void
216			dynbuf_text::add (sint32 i)
217			{
218	root	1.14	force (sint32_digits);
219	root	1.11
220			*ptr = '-'; ptr += i < 0 ? 1 : 0;
221			uint32 u = i < 0 ? -i : i;
222
223			if (expect_true (u < 10)) // we have a lot of single-digit numbers, so optimise
224			fadd (char (u + '0'));
225			else if (expect_true (u < 1000000000)) // 9 0's
226			ptr = i2a_9 (ptr, u, false);
227			else
228	root	1.1	{
229	root	1.11	sint32 div = u / 1000000000;
230			uint32 rem = u % 1000000000;
231	root	1.5
232	root	1.11	ptr = i2a_9 (ptr, div, false);
233			ptr = i2a_9 (ptr, rem, true);
234	root	1.1	}
235			}
236
237	root	1.5	void
238	root	1.7	dynbuf_text::add (sint64 i)
239	root	1.1	{
240	root	1.14	force (sint64_digits);
241	root	1.11
242			*ptr = '-'; ptr += i < 0 ? 1 : 0;
243			uint64 u = i < 0 ? -i : i;
244
245			// split the number into a 1-digit part
246			// (#19) and two 9 digit parts (9..18 and 0..8)
247	root	1.4
248	root	1.11	// good compilers will only use multiplications here
249	root	1.2
250	root	1.11	if (u < 10) // we have a lot of single-digit numbers, so optimise
251			fadd (char (u + '0'));
252			else if (expect_true (u < 1000000000)) // 9 0's
253			ptr = i2a_9 (ptr, u, false);
254			else if (expect_true (u < UINT64_C (1000000000000000000))) // 18 0's
255	root	1.1	{
256	root	1.11	sint32 div = u / 1000000000;
257			uint32 rem = u % 1000000000;
258
259			ptr = i2a_9 (ptr, div, false);
260			ptr = i2a_9 (ptr, rem, true);
261	root	1.1	}
262	root	1.2	else
263	root	1.1	{
264	root	1.11	// a biggy
265			sint32 div = u / UINT64_C (1000000000000000000);
266			uint64 rem = u % UINT64_C (1000000000000000000);
267
268			fadd (char (div + '0'));
269			u = rem;
270
271			{
272			sint32 div = u / 1000000000;
273			uint32 rem = u % 1000000000;
274
275			ptr = i2a_9 (ptr, div, true);
276			ptr = i2a_9 (ptr, rem, true);
277			}
278	root	1.1	}
279	root	1.11	}
280	root	1.1
281	root	1.17	dynbuf_text::operator const char *()
282			{
283			*this << '\0';
284			linearise ();
285			--ptr;
286			return first->data;
287			}
288
289			void
290			dynbuf_text::add_abilities (const char *name, uint32 abilities)
291			{
292			if (!abilities)
293			return;
294
295			*this << '(' << name;
296
297			const char *sep = ": ";
298			for (int i = 0; i < NROFATTACKS; ++i)
299			if (abilities & (1 << i))
300			{
301			*this << sep; sep = ", ";
302			*this << attacks [i];
303			}
304
305			*this << ')';
306			}
307
308			void
309			dynbuf_text::add_paths (const char *name, uint32 paths)
310			{
311			if (!paths)
312			return;
313
314			*this << '(' << name;
315
316			const char *sep = ": ";
317			for (int i = 0; i < NRSPELLPATHS; ++i)
318			if (paths & (1 << i))
319			{
320			*this << sep; sep = ", ";
321			*this << spellpathnames [i];
322			}
323
324			*this << ')';
325			}
326
327	root	1.11	#if 0
328			struct dynbuf_test_class {
329			dynbuf_test_class ()
330			{
331			sint64 s = 0;
332			for (int i = 0; i < 10000000; ++i)
333			{
334			char b1[256], b2[256];
335
336			dynbuf_text db;
337			db.add (s);
338			db.add (char (0));
339
340			db.linearise (b1);
341			sprintf (b2, "%ld", s);
342
343			if (strcmp (b1, b2))
344			printf ("<%s,%s>\n", b1, b2);
345
346			if (i < 20)
347			s = (sint64) pow (10., i);
348			else
349			s = (sint64) exp (random () * (43.6682723752766 / RAND_MAX));
350			}
351
352			exit (0);
353			}
354			} dynbuf_test;
355			#endif
356	root	1.17