#define PY_SSIZE_T_CLEAN

#include "Python.h"

#include "unicodeobject.h"

#include "ucnhash.h"

#ifdef MS_WINDOWS

#include <windows.h>

#define PyUnicode_MAXFREELIST 1024

#define KEEPALIVE_SIZE_LIMIT 9

#ifdef WORDS_BIGENDIAN

# define BYTEORDER_IS_BIG_ENDIAN

# define BYTEORDER_IS_LITTLE_ENDIAN

#ifdef __cplusplus

extern "C" {

static PyUnicodeObject *free_list = NULL;

static int numfree = 0;

static PyUnicodeObject *unicode_empty = NULL;

#define _Py_RETURN_UNICODE_EMPTY() \

do { \

if (unicode_empty != NULL) \

Py_INCREF(unicode_empty); \

else { \

unicode_empty = _PyUnicode_New(0); \

if (unicode_empty != NULL) \

Py_INCREF(unicode_empty); \

} \

return (PyObject *)unicode_empty; \

} while (0)

static PyUnicodeObject *unicode_latin1[256] = {NULL};

static char unicode_default_encoding[100 + 1] = "ascii";

const unsigned char _Py_ascii_whitespace[] = {

0, 0, 0, 0, 0, 0, 0, 0,

0, 1, 1, 1, 1, 1, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 1, 1, 1, 1,

1, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0

};

static unsigned char ascii_linebreak[] = {

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 1, 1, 1, 1, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 1, 1, 1, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0

};

PyUnicode_GetMax(void)

{

#ifdef Py_UNICODE_WIDE

return 0x10FFFF;

/* This is actually an illegal character, so it should

return 0xFFFF;

}

#if LONG_BIT >= 128

#define BLOOM_WIDTH 128

#elif LONG_BIT >= 64

#define BLOOM_WIDTH 64

#elif LONG_BIT >= 32

#define BLOOM_WIDTH 32

#error "LONG_BIT is smaller than 32"

#define BLOOM_MASK unsigned long

static BLOOM_MASK bloom_linebreak = ~(BLOOM_MASK)0;

#define BLOOM_ADD(mask, ch) ((mask |= (1UL << ((ch) & (BLOOM_WIDTH - 1)))))

#define BLOOM(mask, ch) ((mask & (1UL << ((ch) & (BLOOM_WIDTH - 1)))))

#define BLOOM_LINEBREAK(ch) \

((ch) < 128U ? ascii_linebreak[(ch)] : \

(BLOOM(bloom_linebreak, (ch)) && Py_UNICODE_ISLINEBREAK(ch)))

Py_LOCAL_INLINE(BLOOM_MASK) make_bloom_mask(Py_UNICODE* ptr, Py_ssize_t len)

{

/* calculate simple bloom-style bitmask for a given unicode string */

BLOOM_MASK mask;

Py_ssize_t i;

mask = 0;

for (i = 0; i < len; i++)

BLOOM_ADD(mask, ptr[i]);

return mask;

}

Py_LOCAL_INLINE(int) unicode_member(Py_UNICODE chr, Py_UNICODE* set, Py_ssize_t setlen)

{

Py_ssize_t i;

for (i = 0; i < setlen; i++)

if (set[i] == chr)

return 1;

return 0;

}

#define BLOOM_MEMBER(mask, chr, set, setlen) \

BLOOM(mask, chr) && unicode_member(chr, set, setlen)

int unicode_resize(register PyUnicodeObject *unicode,

Py_ssize_t length)

{

void *oldstr;

/* Shortcut if there's nothing much to do. */

if (unicode->length == length)

goto reset;

/* Resizing shared object (unicode_empty or single character

if (unicode == unicode_empty ||

(unicode->length == 1 &&

unicode->str[0] < 256U &&

unicode_latin1[unicode->str[0]] == unicode)) {

PyErr_SetString(PyExc_SystemError,

"can't resize shared unicode objects");

return -1;

}

/* We allocate one more byte to make sure the string is Ux0000 terminated.

oldstr = unicode->str;

unicode->str = PyObject_REALLOC(unicode->str,

sizeof(Py_UNICODE) * (length + 1));

if (!unicode->str) {

unicode->str = (Py_UNICODE *)oldstr;

PyErr_NoMemory();

return -1;

}

unicode->str[length] = 0;

unicode->length = length;

reset:

/* Reset the object caches */

if (unicode->defenc) {

Py_CLEAR(unicode->defenc);

}

unicode->hash = -1;

return 0;

}

PyUnicodeObject *_PyUnicode_New(Py_ssize_t length)

{

register PyUnicodeObject *unicode;

/* Optimization for empty strings */

if (length == 0 && unicode_empty != NULL) {

Py_INCREF(unicode_empty);

return unicode_empty;

}

/* Ensure we won't overflow the size. */

if (length > ((PY_SSIZE_T_MAX / sizeof(Py_UNICODE)) - 1)) {

return (PyUnicodeObject *)PyErr_NoMemory();

}

/* Unicode freelist & memory allocation */

if (free_list) {

unicode = free_list;

free_list = *(PyUnicodeObject **)unicode;

numfree--;

if (unicode->str) {

/* Keep-Alive optimization: we only upsize the buffer,

if ((unicode->length < length) &&

unicode_resize(unicode, length) < 0) {

PyObject_DEL(unicode->str);

unicode->str = NULL;

}

}

else {

size_t new_size = sizeof(Py_UNICODE) * ((size_t)length + 1);

unicode->str = (Py_UNICODE*) PyObject_MALLOC(new_size);

}

PyObject_INIT(unicode, &PyUnicode_Type);

}

else {

size_t new_size;

unicode = PyObject_New(PyUnicodeObject, &PyUnicode_Type);

if (unicode == NULL)

return NULL;

new_size = sizeof(Py_UNICODE) * ((size_t)length + 1);

unicode->str = (Py_UNICODE*) PyObject_MALLOC(new_size);

}

if (!unicode->str) {

PyErr_NoMemory();

goto onError;

}

/* Initialize the first element to guard against cases where

unicode->str[0] = 0;

unicode->str[length] = 0;

unicode->length = length;

unicode->hash = -1;

unicode->defenc = NULL;

return unicode;

onError:

/* XXX UNREF/NEWREF interface should be more symmetrical */

_Py_DEC_REFTOTAL;

_Py_ForgetReference((PyObject *)unicode);

PyObject_Del(unicode);

return NULL;

}

void unicode_dealloc(register PyUnicodeObject *unicode)

{

if (PyUnicode_CheckExact(unicode) &&

numfree < PyUnicode_MAXFREELIST) {

/* Keep-Alive optimization */

if (unicode->length >= KEEPALIVE_SIZE_LIMIT) {

PyObject_DEL(unicode->str);

unicode->str = NULL;

unicode->length = 0;

}

if (unicode->defenc) {

Py_CLEAR(unicode->defenc);

}

/* Add to free list */

*(PyUnicodeObject **)unicode = free_list;

free_list = unicode;

numfree++;

}

else {

PyObject_DEL(unicode->str);

Py_XDECREF(unicode->defenc);

Py_TYPE(unicode)->tp_free((PyObject *)unicode);

}

}

int _PyUnicode_Resize(PyUnicodeObject **unicode, Py_ssize_t length)

{

register PyUnicodeObject *v;

/* Argument checks */

if (unicode == NULL) {

PyErr_BadInternalCall();

return -1;

}

v = *unicode;

if (v == NULL || !PyUnicode_Check(v) || Py_REFCNT(v) != 1 || length < 0) {

PyErr_BadInternalCall();

return -1;

}

/* Resizing unicode_empty and single character objects is not

if (v->length != length &&

(v == unicode_empty || v->length == 1)) {

PyUnicodeObject *w = _PyUnicode_New(length);

if (w == NULL)

return -1;

Py_UNICODE_COPY(w->str, v->str,

length < v->length ? length : v->length);

Py_DECREF(*unicode);

*unicode = w;

return 0;

}

/* Note that we don't have to modify *unicode for unshared Unicode

return unicode_resize(v, length);

}

int PyUnicode_Resize(PyObject **unicode, Py_ssize_t length)

{

return _PyUnicode_Resize((PyUnicodeObject **)unicode, length);

}

PyObject *PyUnicode_FromUnicode(const Py_UNICODE *u,

Py_ssize_t size)

{

PyUnicodeObject *unicode;

/* If the Unicode data is known at construction time, we can apply

if (u != NULL) {

/* Optimization for empty strings */

if (size == 0)

_Py_RETURN_UNICODE_EMPTY();

/* Single character Unicode objects in the Latin-1 range are

if (size == 1 && *u < 256) {

unicode = unicode_latin1[*u];

if (!unicode) {

unicode = _PyUnicode_New(1);

if (!unicode)

return NULL;

unicode->str[0] = *u;

unicode_latin1[*u] = unicode;

}

Py_INCREF(unicode);

return (PyObject *)unicode;

}

}

unicode = _PyUnicode_New(size);

if (!unicode)

return NULL;

/* Copy the Unicode data into the new object */

if (u != NULL)

Py_UNICODE_COPY(unicode->str, u, size);

return (PyObject *)unicode;

}

PyObject *PyUnicode_FromStringAndSize(const char *u, Py_ssize_t size)

{

PyUnicodeObject *unicode;

if (size < 0) {

PyErr_SetString(PyExc_SystemError,

"Negative size passed to PyUnicode_FromStringAndSize");

return NULL;

}

/* If the Unicode data is known at construction time, we can apply

if (u != NULL) {

/* Optimization for empty strings */

if (size == 0)

_Py_RETURN_UNICODE_EMPTY();

/* Single characters are shared when using this constructor.

if (size == 1 && Py_CHARMASK(*u) < 128) {

unicode = unicode_latin1[Py_CHARMASK(*u)];

if (!unicode) {

unicode = _PyUnicode_New(1);

if (!unicode)

return NULL;

unicode->str[0] = Py_CHARMASK(*u);

unicode_latin1[Py_CHARMASK(*u)] = unicode;

}

Py_INCREF(unicode);

return (PyObject *)unicode;

}

return PyUnicode_DecodeUTF8(u, size, NULL);

}

unicode = _PyUnicode_New(size);

if (!unicode)

return NULL;

return (PyObject *)unicode;

}

PyObject *PyUnicode_FromString(const char *u)

{

size_t size = strlen(u);

if (size > PY_SSIZE_T_MAX) {

PyErr_SetString(PyExc_OverflowError, "input too long");

return NULL;

}

return PyUnicode_FromStringAndSize(u, size);

}

#define _Py_UNICODE_IS_HIGH_SURROGATE(ch) (0xD800 <= ch && ch <= 0xDBFF)

#define _Py_UNICODE_IS_LOW_SURROGATE(ch) (0xDC00 <= ch && ch <= 0xDFFF)

#define _Py_UNICODE_JOIN_SURROGATES(high, low) \

(((((Py_UCS4)(high) & 0x03FF) << 10) | \

((Py_UCS4)(low) & 0x03FF)) + 0x10000)

#ifdef Py_UNICODE_WIDE

#define _Py_UNICODE_NEXT(ptr, end) *(ptr)++

#define _Py_UNICODE_NEXT(ptr, end) \

(((_Py_UNICODE_IS_HIGH_SURROGATE(*(ptr)) && (ptr) < (end)) && \

_Py_UNICODE_IS_LOW_SURROGATE((ptr)[1])) ? \

((ptr) += 2,_Py_UNICODE_JOIN_SURROGATES((ptr)[-2], (ptr)[-1])) : \

(Py_UCS4)*(ptr)++)

#ifdef HAVE_WCHAR_H

#if (Py_UNICODE_SIZE == 2) && defined(SIZEOF_WCHAR_T) && (SIZEOF_WCHAR_T == 4)

# define CONVERT_WCHAR_TO_SURROGATES

#ifdef CONVERT_WCHAR_TO_SURROGATES

PyObject *PyUnicode_FromWideChar(register const wchar_t *w,

Py_ssize_t size)

{

PyUnicodeObject *unicode;

register Py_ssize_t i;

Py_ssize_t alloc;

const wchar_t *orig_w;

if (w == NULL) {

PyErr_BadInternalCall();

return NULL;

}

alloc = size;

orig_w = w;

for (i = size; i > 0; i--) {

if (*w > 0xFFFF)

alloc++;

w++;

}

w = orig_w;

unicode = _PyUnicode_New(alloc);

if (!unicode)

return NULL;

/* Copy the wchar_t data into the new object */

{

register Py_UNICODE *u;

u = PyUnicode_AS_UNICODE(unicode);

for (i = size; i > 0; i--) {

if (*w > 0xFFFF) {

wchar_t ordinal = *w++;

ordinal -= 0x10000;

*u++ = 0xD800 | (ordinal >> 10);

*u++ = 0xDC00 | (ordinal & 0x3FF);

}

else

*u++ = *w++;

}

}

return (PyObject *)unicode;

}

PyObject *PyUnicode_FromWideChar(register const wchar_t *w,

Py_ssize_t size)

{

PyUnicodeObject *unicode;

if (w == NULL) {

PyErr_BadInternalCall();

return NULL;

}

unicode = _PyUnicode_New(size);

if (!unicode)

return NULL;

/* Copy the wchar_t data into the new object */

#ifdef HAVE_USABLE_WCHAR_T

memcpy(unicode->str, w, size * sizeof(wchar_t));

{

register Py_UNICODE *u;

register Py_ssize_t i;

u = PyUnicode_AS_UNICODE(unicode);

for (i = size; i > 0; i--)

*u++ = *w++;

}

return (PyObject *)unicode;

}

#endif /* CONVERT_WCHAR_TO_SURROGATES */

#undef CONVERT_WCHAR_TO_SURROGATES

static void

makefmt(char *fmt, int longflag, int size_tflag, int zeropad, int width, int precision, char c)

{

*fmt++ = '%';

if (width) {

if (zeropad)

*fmt++ = '0';

fmt += sprintf(fmt, "%d", width);

}

if (precision)

fmt += sprintf(fmt, ".%d", precision);

if (longflag)

*fmt++ = 'l';

else if (size_tflag) {

char *f = PY_FORMAT_SIZE_T;

while (*f)

*fmt++ = *f++;

}

*fmt++ = c;

*fmt = '\0';

}

#define appendstring(string) \

do { \

for (copy = string;*copy; copy++) { \

*s++ = (unsigned char)*copy; \

} \

} while (0)

PyObject *

PyUnicode_FromFormatV(const char *format, va_list vargs)

{

va_list count;

Py_ssize_t callcount = 0;

PyObject **callresults = NULL;

PyObject **callresult = NULL;

Py_ssize_t n = 0;

int width = 0;

int precision = 0;

int zeropad;

const char* f;

Py_UNICODE *s;

PyObject *string;

/* used by sprintf */

char buffer[21];

/* use abuffer instead of buffer, if we need more space

char *abuffer = NULL;

char *realbuffer;

Py_ssize_t abuffersize = 0;

char fmt[60]; /* should be enough for %0width.precisionld */

const char *copy;

#ifdef VA_LIST_IS_ARRAY

Py_MEMCPY(count, vargs, sizeof(va_list));

#ifdef __va_copy

__va_copy(count, vargs);

count = vargs;

/* step 1: count the number of %S/%R/%s format specifications

for (f = format; *f; f++) {

if (*f == '%') {

f++;

while (*f && *f != '%' && !isalpha((unsigned)*f))

f++;

if (!*f)

break;

if (*f == 's' || *f=='S' || *f=='R')

++callcount;

}

}

/* step 2: allocate memory for the results of

if (callcount) {

callresults = PyObject_Malloc(sizeof(PyObject *)*callcount);

if (!callresults) {

PyErr_NoMemory();

return NULL;

}

callresult = callresults;

}

/* step 3: figure out how large a buffer we need */

for (f = format; *f; f++) {

if (*f == '%') {

const char* p = f++;

width = 0;

while (isdigit((unsigned)*f))

width = (width*10) + *f++ - '0';

precision = 0;

if (*f == '.') {

f++;

while (isdigit((unsigned)*f))

precision = (precision*10) + *f++ - '0';

}

/* skip the 'l' or 'z' in {%ld, %zd, %lu, %zu} since

if ((*f == 'l' || *f == 'z') &&

(f[1] == 'd' || f[1] == 'u'))

++f;

switch (*f) {

case 'c':

{

int ordinal = va_arg(count, int);

#ifdef Py_UNICODE_WIDE

if (ordinal < 0 || ordinal > 0x10ffff) {

PyErr_SetString(PyExc_OverflowError,

"%c arg not in range(0x110000) "

"(wide Python build)");

goto fail;

}

if (ordinal < 0 || ordinal > 0xffff) {

PyErr_SetString(PyExc_OverflowError,

"%c arg not in range(0x10000) "

"(narrow Python build)");

goto fail;

}

/* fall through... */

}

case '%':

n++;

break;

case 'd': case 'u': case 'i': case 'x':

(void) va_arg(count, int);

if (width < precision)

width = precision;

/* 20 bytes is enough to hold a 64-bit

if (width < 20)

width = 20;

n += width;

if (abuffersize < width)

abuffersize = width;

break;

case 's':

{

/* UTF-8 */

const char *s = va_arg(count, const char*);

PyObject *str = PyUnicode_DecodeUTF8(s, strlen(s), "replace");

if (!str)

goto fail;

n += PyUnicode_GET_SIZE(str);

/* Remember the str and switch to the next slot */

*callresult++ = str;

break;

}

case 'U':

{

PyObject *obj = va_arg(count, PyObject *);

assert(obj && PyUnicode_Check(obj));

n += PyUnicode_GET_SIZE(obj);

break;

}

case 'V':

{

PyObject *obj = va_arg(count, PyObject *);

const char *str = va_arg(count, const char *);

assert(obj || str);

assert(!obj || PyUnicode_Check(obj));

if (obj)

n += PyUnicode_GET_SIZE(obj);

else

n += strlen(str);

break;

}

case 'S':

{

PyObject *obj = va_arg(count, PyObject *);

PyObject *str;

assert(obj);

str = PyObject_Str(obj);

if (!str)

goto fail;

n += PyString_GET_SIZE(str);

/* Remember the str and switch to the next slot */

*callresult++ = str;

break;

}

case 'R':

{

PyObject *obj = va_arg(count, PyObject *);

PyObject *repr;

assert(obj);

repr = PyObject_Repr(obj);

if (!repr)

goto fail;

n += PyUnicode_GET_SIZE(repr);

/* Remember the repr and switch to the next slot */

*callresult++ = repr;

break;

}

case 'p':

(void) va_arg(count, int);

/* maximum 64-bit pointer representation:

n += 19;

break;

default:

/* if we stumble upon an unknown

n += strlen(p);

goto expand;

}

} else

n++;

}

expand:

if (abuffersize > 20) {

/* add 1 for sprintf's trailing null byte */

abuffer = PyObject_Malloc(abuffersize + 1);

if (!abuffer) {

PyErr_NoMemory();

goto fail;

}

realbuffer = abuffer;

}

else

realbuffer = buffer;

/* step 4: fill the buffer */

/* Since we've analyzed how much space we need for the worst case,

string = PyUnicode_FromUnicode(NULL, n);

if (!string)

goto fail;

s = PyUnicode_AS_UNICODE(string);

callresult = callresults;

for (f = format; *f; f++) {

if (*f == '%') {

const char* p = f++;

int longflag = 0;

int size_tflag = 0;

zeropad = (*f == '0');

/* parse the width.precision part */

width = 0;

while (isdigit((unsigned)*f))

width = (width*10) + *f++ - '0';

precision = 0;

if (*f == '.') {

f++;

while (isdigit((unsigned)*f))

precision = (precision*10) + *f++ - '0';

}

/* handle the long flag, but only for %ld and %lu.

if (*f == 'l' && (f[1] == 'd' || f[1] == 'u')) {

longflag = 1;

++f;

}

/* handle the size_t flag. */

if (*f == 'z' && (f[1] == 'd' || f[1] == 'u')) {

size_tflag = 1;

++f;

}

switch (*f) {

case 'c':

*s++ = va_arg(vargs, int);

break;

case 'd':

makefmt(fmt, longflag, size_tflag, zeropad, width, precision, 'd');

if (longflag)

sprintf(realbuffer, fmt, va_arg(vargs, long));

else if (size_tflag)

sprintf(realbuffer, fmt, va_arg(vargs, Py_ssize_t));

else

sprintf(realbuffer, fmt, va_arg(vargs, int));

appendstring(realbuffer);

break;

case 'u':

makefmt(fmt, longflag, size_tflag, zeropad, width, precision, 'u');

if (longflag)

sprintf(realbuffer, fmt, va_arg(vargs, unsigned long));

else if (size_tflag)

sprintf(realbuffer, fmt, va_arg(vargs, size_t));

else

sprintf(realbuffer, fmt, va_arg(vargs, unsigned int));

appendstring(realbuffer);

break;

case 'i':

makefmt(fmt, 0, 0, zeropad, width, precision, 'i');

sprintf(realbuffer, fmt, va_arg(vargs, int));

appendstring(realbuffer);

break;

case 'x':

makefmt(fmt, 0, 0, zeropad, width, precision, 'x');

sprintf(realbuffer, fmt, va_arg(vargs, int));

appendstring(realbuffer);

break;

case 's':

{

/* unused, since we already have the result */

(void) va_arg(vargs, char *);

Py_UNICODE_COPY(s, PyUnicode_AS_UNICODE(*callresult),

PyUnicode_GET_SIZE(*callresult));

s += PyUnicode_GET_SIZE(*callresult);

/* We're done with the unicode()/repr() => forget it */

Py_DECREF(*callresult);

/* switch to next unicode()/repr() result */

++callresult;

break;

}

case 'U':

{

PyObject *obj = va_arg(vargs, PyObject *);

Py_ssize_t size = PyUnicode_GET_SIZE(obj);

Py_UNICODE_COPY(s, PyUnicode_AS_UNICODE(obj), size);

s += size;

break;