/* struct module -- pack values into and (out of) bytes objects */

/* New version supporting byte order, alignment and size options,
   character strings, and unsigned numbers */

#ifndef Py_BUILD_CORE_BUILTIN
#  define Py_BUILD_CORE_MODULE 1
#endif

#include "Python.h"
#include "pycore_bytesobject.h"   // _PyBytesWriter
#include "pycore_lock.h"          // _PyOnceFlag_CallOnce()
#include "pycore_long.h"          // _PyLong_AsByteArray()
#include "pycore_moduleobject.h"  // _PyModule_GetState()
#include "pycore_weakref.h"       // FT_CLEAR_WEAKREFS()

#include <stddef.h>               // offsetof()

/*[clinic input]
class Struct "PyStructObject *" "&PyStructType"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=9b032058a83ed7c3]*/

typedef struct {
    PyObject *cache;
    PyObject *PyStructType;
    PyObject *unpackiter_type;
    PyObject *StructError;
} _structmodulestate;

static inline _structmodulestate*
get_struct_state(PyObject *module)
{
    void *state = _PyModule_GetState(module);
    assert(state != NULL);
    return (_structmodulestate *)state;
}

static struct PyModuleDef _structmodule;

#define get_struct_state_structinst(self) \
    (get_struct_state(PyType_GetModuleByDef(Py_TYPE(self), &_structmodule)))
#define get_struct_state_iterinst(self) \
    (get_struct_state(PyType_GetModule(Py_TYPE(self))))

/* The translation function for each format character is table driven */
typedef struct _formatdef {
    char format;
    Py_ssize_t size;
    Py_ssize_t alignment;
    PyObject* (*unpack)(_structmodulestate *, const char *,
                        const struct _formatdef *);
    int (*pack)(_structmodulestate *, char *, PyObject *,
                const struct _formatdef *);
} formatdef;

typedef struct _formatcode {
    const struct _formatdef *fmtdef;
    Py_ssize_t offset;
    Py_ssize_t size;
    Py_ssize_t repeat;
} formatcode;

/* Struct object interface */

typedef struct {
    PyObject_HEAD
    Py_ssize_t s_size;
    Py_ssize_t s_len;
    formatcode *s_codes;
    PyObject *s_format;
    PyObject *weakreflist; /* List of weak references */
    bool init_called;
} PyStructObject;

#define PyStructObject_CAST(op)     ((PyStructObject *)(op))
#define PyStruct_Check(op, state)   PyObject_TypeCheck(op, (PyTypeObject *)(state)->PyStructType)

#ifdef __powerc
#pragma options align=reset
#endif

/*[python input]
class cache_struct_converter(CConverter):
    type = 'PyStructObject *'
    converter = 'cache_struct_converter'
    c_default = "NULL"
    broken_limited_capi = True

    def parse_arg(self, argname, displayname, *, limited_capi):
        assert not limited_capi
        return self.format_code("""
            if (!{converter}(module, {argname}, &{paramname})) {{{{
                goto exit;
            }}}}
            """,
            argname=argname,
            converter=self.converter)

    def cleanup(self):
        return "Py_XDECREF(%s);\n" % self.name
[python start generated code]*/
/*[python end generated code: output=da39a3ee5e6b4b0d input=c33b27d6b06006c6]*/

static int cache_struct_converter(PyObject *, PyObject *, PyStructObject **);

#include "clinic/_struct.c.h"

/* Helper for integer format codes: converts an arbitrary Python object to a
   PyLongObject if possible, otherwise fails.  Caller should decref. */

static PyObject *
get_pylong(_structmodulestate *state, PyObject *v)
{
    assert(v != NULL);
    if (!PyLong_Check(v)) {
        /* Not an integer;  try to use __index__ to convert. */
        if (PyIndex_Check(v)) {
            v = _PyNumber_Index(v);
            if (v == NULL)
                return NULL;
        }
        else {
            PyErr_SetString(state->StructError,
                            "required argument is not an integer");
            return NULL;
        }
    }
    else
        Py_INCREF(v);

    assert(PyLong_Check(v));
    return v;
}

/* Helper routine to get a C long and raise the appropriate error if it isn't
   one */

static int
get_long(_structmodulestate *state, PyObject *v, long *p)
{
    long x;

    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    assert(PyLong_Check(v));
    x = PyLong_AsLong(v);
    Py_DECREF(v);
    if (x == (long)-1 && PyErr_Occurred()) {
        return -1;
    }
    *p = x;
    return 0;
}


/* Same, but handling unsigned long */

static int
get_ulong(_structmodulestate *state, PyObject *v, unsigned long *p)
{
    unsigned long x;

    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    assert(PyLong_Check(v));
    x = PyLong_AsUnsignedLong(v);
    Py_DECREF(v);
    if (x == (unsigned long)-1 && PyErr_Occurred()) {
        return -1;
    }
    *p = x;
    return 0;
}

/* Same, but handling native long long. */

static int
get_longlong(_structmodulestate *state, PyObject *v, long long *p)
{
    long long x;

    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    assert(PyLong_Check(v));
    x = PyLong_AsLongLong(v);
    Py_DECREF(v);
    if (x == (long long)-1 && PyErr_Occurred()) {
        return -1;
    }
    *p = x;
    return 0;
}

/* Same, but handling native unsigned long long. */

static int
get_ulonglong(_structmodulestate *state, PyObject *v, unsigned long long *p)
{
    unsigned long long x;

    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    assert(PyLong_Check(v));
    x = PyLong_AsUnsignedLongLong(v);
    Py_DECREF(v);
    if (x == (unsigned long long)-1 && PyErr_Occurred()) {
        return -1;
    }
    *p = x;
    return 0;
}

/* Same, but handling Py_ssize_t */

static int
get_ssize_t(_structmodulestate *state, PyObject *v, Py_ssize_t *p)
{
    Py_ssize_t x;

    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    assert(PyLong_Check(v));
    x = PyLong_AsSsize_t(v);
    Py_DECREF(v);
    if (x == (Py_ssize_t)-1 && PyErr_Occurred()) {
        return -1;
    }
    *p = x;
    return 0;
}

/* Same, but handling size_t */

static int
get_size_t(_structmodulestate *state, PyObject *v, size_t *p)
{
    size_t x;

    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    assert(PyLong_Check(v));
    x = PyLong_AsSize_t(v);
    Py_DECREF(v);
    if (x == (size_t)-1 && PyErr_Occurred()) {
        return -1;
    }
    *p = x;
    return 0;
}


#define RANGE_ERROR(state, f, flag) return _range_error(state, f, flag)


/* Floating-point helpers */

static PyObject *
unpack_halffloat(const char *p,  /* start of 2-byte string */
                 int le)         /* true for little-endian, false for big-endian */
{
    double x = PyFloat_Unpack2(p, le);
    if (x == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    return PyFloat_FromDouble(x);
}

static int
pack_halffloat(_structmodulestate *state,
               char *p,      /* start of 2-byte string */
               PyObject *v,  /* value to pack */
               int le)       /* true for little-endian, false for big-endian */
{
    double x = PyFloat_AsDouble(v);
    if (x == -1.0 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a float");
        return -1;
    }
    return PyFloat_Pack2(x, p, le);
}

static PyObject *
unpack_float(const char *p,  /* start of 4-byte string */
         int le)             /* true for little-endian, false for big-endian */
{
    double x;

    x = PyFloat_Unpack4(p, le);
    if (x == -1.0 && PyErr_Occurred())
        return NULL;
    return PyFloat_FromDouble(x);
}

static PyObject *
unpack_double(const char *p,  /* start of 8-byte string */
          int le)         /* true for little-endian, false for big-endian */
{
    double x;

    x = PyFloat_Unpack8(p, le);
    if (x == -1.0 && PyErr_Occurred())
        return NULL;
    return PyFloat_FromDouble(x);
}

/* Helper to format the range error exceptions */
static int
_range_error(_structmodulestate *state, const formatdef *f, int is_unsigned)
{
    /* ulargest is the largest unsigned value with f->size bytes.
     * Note that the simpler:
     *     ((size_t)1 << (f->size * 8)) - 1
     * doesn't work when f->size == sizeof(size_t) because C doesn't
     * define what happens when a left shift count is >= the number of
     * bits in the integer being shifted; e.g., on some boxes it doesn't
     * shift at all when they're equal.
     */
    const size_t ulargest = (size_t)-1 >> ((SIZEOF_SIZE_T - f->size)*8);
    assert(f->size >= 1 && f->size <= SIZEOF_SIZE_T);
    if (is_unsigned)
        PyErr_Format(state->StructError,
            "'%c' format requires 0 <= number <= %zu",
            f->format,
            ulargest);
    else {
        const Py_ssize_t largest = (Py_ssize_t)(ulargest >> 1);
        PyErr_Format(state->StructError,
            "'%c' format requires %zd <= number <= %zd",
            f->format,
            ~ largest,
            largest);
    }

    return -1;
}


/* A large number of small routines follow, with names of the form

   [bln][up]_TYPE

   [bln] distinguishes among big-endian, little-endian and native.
   [pu] distinguishes between pack (to struct) and unpack (from struct).
   TYPE is one of char, byte, ubyte, etc.
*/

/* Native mode routines. ****************************************************/
/* NOTE:
   In all n[up]_<type> routines handling types larger than 1 byte, there is
   *no* guarantee that the p pointer is properly aligned for each type,
   therefore memcpy is called.  An intermediate variable is used to
   compensate for big-endian architectures.
   Normally both the intermediate variable and the memcpy call will be
   skipped by C optimisation in little-endian architectures (gcc >= 2.91
   does this). */

static PyObject *
nu_char(_structmodulestate *state, const char *p, const formatdef *f)
{
    return PyBytes_FromStringAndSize(p, 1);
}

static PyObject *
nu_byte(_structmodulestate *state, const char *p, const formatdef *f)
{
    return PyLong_FromLong((long) *(signed char *)p);
}

static PyObject *
nu_ubyte(_structmodulestate *state, const char *p, const formatdef *f)
{
    return PyLong_FromLong((long) *(unsigned char *)p);
}

static PyObject *
nu_short(_structmodulestate *state, const char *p, const formatdef *f)
{
    short x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromLong((long)x);
}

static PyObject *
nu_ushort(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned short x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromLong((long)x);
}

static PyObject *
nu_int(_structmodulestate *state, const char *p, const formatdef *f)
{
    int x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromLong((long)x);
}

static PyObject *
nu_uint(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned int x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromUnsignedLong((unsigned long)x);
}

static PyObject *
nu_long(_structmodulestate *state, const char *p, const formatdef *f)
{
    long x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromLong(x);
}

static PyObject *
nu_ulong(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromUnsignedLong(x);
}

static PyObject *
nu_ssize_t(_structmodulestate *state, const char *p, const formatdef *f)
{
    Py_ssize_t x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromSsize_t(x);
}

static PyObject *
nu_size_t(_structmodulestate *state, const char *p, const formatdef *f)
{
    size_t x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromSize_t(x);
}

static PyObject *
nu_longlong(_structmodulestate *state, const char *p, const formatdef *f)
{
    long long x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromLongLong(x);
}

static PyObject *
nu_ulonglong(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long long x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromUnsignedLongLong(x);
}

static PyObject *
nu_bool(_structmodulestate *state, const char *p, const formatdef *f)
{
    const _Bool bool_false = 0;
    return PyBool_FromLong(memcmp(p, &bool_false, sizeof(_Bool)));
}


static PyObject *
nu_halffloat(_structmodulestate *state, const char *p, const formatdef *f)
{
#if PY_LITTLE_ENDIAN
    return unpack_halffloat(p, 1);
#else
    return unpack_halffloat(p, 0);
#endif
}

static PyObject *
nu_float(_structmodulestate *state, const char *p, const formatdef *f)
{
    float x;
    memcpy(&x, p, sizeof x);
    return PyFloat_FromDouble((double)x);
}

static PyObject *
nu_double(_structmodulestate *state, const char *p, const formatdef *f)
{
    double x;
    memcpy(&x, p, sizeof x);
    return PyFloat_FromDouble(x);
}

static PyObject *
nu_float_complex(_structmodulestate *state, const char *p, const formatdef *f)
{
    float x[2];

    memcpy(&x, p, sizeof(x));
    return PyComplex_FromDoubles(x[0], x[1]);
}

static PyObject *
nu_double_complex(_structmodulestate *state, const char *p, const formatdef *f)
{
    double x[2];

    memcpy(&x, p, sizeof(x));
    return PyComplex_FromDoubles(x[0], x[1]);
}

static PyObject *
nu_void_p(_structmodulestate *state, const char *p, const formatdef *f)
{
    void *x;
    memcpy(&x, p, sizeof x);
    return PyLong_FromVoidPtr(x);
}

static int
np_byte(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long x;
    if (get_long(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 0);
        }
        return -1;
    }
    if (x < -128 || x > 127) {
        RANGE_ERROR(state, f, 0);
    }
    *p = (char)x;
    return 0;
}

static int
np_ubyte(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long x;
    if (get_long(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 1);
        }
        return -1;
    }
    if (x < 0 || x > 255) {
        RANGE_ERROR(state, f, 1);
    }
    *(unsigned char *)p = (unsigned char)x;
    return 0;
}

static int
np_char(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    if (!PyBytes_Check(v) || PyBytes_Size(v) != 1) {
        PyErr_SetString(state->StructError,
                        "char format requires a bytes object of length 1");
        return -1;
    }
    *p = *PyBytes_AS_STRING(v);
    return 0;
}

static int
np_short(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long x;
    short y;
    if (get_long(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 0);
        }
        return -1;
    }
    if (x < SHRT_MIN || x > SHRT_MAX) {
        RANGE_ERROR(state, f, 0);
    }
    y = (short)x;
    memcpy(p, &y, sizeof y);
    return 0;
}

static int
np_ushort(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long x;
    unsigned short y;
    if (get_long(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 1);
        }
        return -1;
    }
    if (x < 0 || x > USHRT_MAX) {
        RANGE_ERROR(state, f, 1);
    }
    y = (unsigned short)x;
    memcpy(p, &y, sizeof y);
    return 0;
}

static int
np_int(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long x;
    int y;
    if (get_long(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 0);
        }
        return -1;
    }
#if (SIZEOF_LONG > SIZEOF_INT)
    if ((x < ((long)INT_MIN)) || (x > ((long)INT_MAX)))
        RANGE_ERROR(state, f, 0);
#endif
    y = (int)x;
    memcpy(p, &y, sizeof y);
    return 0;
}

static int
np_uint(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    unsigned long x;
    unsigned int y;
    if (get_ulong(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 1);
        }
        return -1;
    }
    y = (unsigned int)x;
#if (SIZEOF_LONG > SIZEOF_INT)
    if (x > ((unsigned long)UINT_MAX))
        RANGE_ERROR(state, f, 1);
#endif
    memcpy(p, &y, sizeof y);
    return 0;
}

static int
np_long(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long x;
    if (get_long(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 0);
        }
        return -1;
    }
    memcpy(p, &x, sizeof x);
    return 0;
}

static int
np_ulong(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    unsigned long x;
    if (get_ulong(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 1);
        }
        return -1;
    }
    memcpy(p, &x, sizeof x);
    return 0;
}

static int
np_ssize_t(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    Py_ssize_t x;
    if (get_ssize_t(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 0);
        }
        return -1;
    }
    memcpy(p, &x, sizeof x);
    return 0;
}

static int
np_size_t(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    size_t x;
    if (get_size_t(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 1);
        }
        return -1;
    }
    memcpy(p, &x, sizeof x);
    return 0;
}

static int
np_longlong(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long long x;
    if (get_longlong(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            PyErr_Format(state->StructError,
                         "'%c' format requires %lld <= number <= %lld",
                         f->format,
                         LLONG_MIN,
                         LLONG_MAX);
        }
        return -1;
    }
    memcpy(p, &x, sizeof x);
    return 0;
}

static int
np_ulonglong(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    unsigned long long x;
    if (get_ulonglong(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            PyErr_Format(state->StructError,
                         "'%c' format requires 0 <= number <= %llu",
                         f->format,
                         ULLONG_MAX);
        }
        return -1;
    }
    memcpy(p, &x, sizeof x);
    return 0;
}


static int
np_bool(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    int y;
    _Bool x;
    y = PyObject_IsTrue(v);
    if (y < 0)
        return -1;
    x = y;
    memcpy(p, &x, sizeof x);
    return 0;
}

static int
np_halffloat(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
#if PY_LITTLE_ENDIAN
    return pack_halffloat(state, p, v, 1);
#else
    return pack_halffloat(state, p, v, 0);
#endif
}

static int
np_float(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    float x = (float)PyFloat_AsDouble(v);
    if (x == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a float");
        return -1;
    }
    memcpy(p, &x, sizeof x);
    return 0;
}

static int
np_double(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    double x = PyFloat_AsDouble(v);
    if (x == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a float");
        return -1;
    }
    memcpy(p, &x, sizeof(double));
    return 0;
}

static int
np_float_complex(_structmodulestate *state, char *p, PyObject *v,
                 const formatdef *f)
{
    Py_complex c = PyComplex_AsCComplex(v);
    float x[2] = {(float)c.real, (float)c.imag};

    if (c.real == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a complex");
        return -1;
    }
    memcpy(p, &x, sizeof(x));
    return 0;
}

static int
np_double_complex(_structmodulestate *state, char *p, PyObject *v,
                  const formatdef *f)
{
    Py_complex c = PyComplex_AsCComplex(v);
    double x[2] = {c.real, c.imag};

    if (c.real == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a complex");
        return -1;
    }
    memcpy(p, &x, sizeof(x));
    return 0;
}

static int
np_void_p(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    void *x;

    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    assert(PyLong_Check(v));
    x = PyLong_AsVoidPtr(v);
    Py_DECREF(v);
    if (x == NULL && PyErr_Occurred())
        return -1;
    memcpy(p, &x, sizeof x);
    return 0;
}

static const formatdef native_table[] = {
    {'x',       sizeof(char),   0,              NULL},
    {'b',       sizeof(char),   0,              nu_byte,        np_byte},
    {'B',       sizeof(char),   0,              nu_ubyte,       np_ubyte},
    {'c',       sizeof(char),   0,              nu_char,        np_char},
    {'s',       sizeof(char),   0,              NULL},
    {'p',       sizeof(char),   0,              NULL},
    {'h',       sizeof(short),  _Alignof(short),    nu_short,       np_short},
    {'H',       sizeof(short),  _Alignof(short),    nu_ushort,      np_ushort},
    {'i',       sizeof(int),    _Alignof(int),      nu_int,         np_int},
    {'I',       sizeof(int),    _Alignof(int),      nu_uint,        np_uint},
    {'l',       sizeof(long),   _Alignof(long),     nu_long,        np_long},
    {'L',       sizeof(long),   _Alignof(long),     nu_ulong,       np_ulong},
    {'n',       sizeof(size_t), _Alignof(size_t),   nu_ssize_t,     np_ssize_t},
    {'N',       sizeof(size_t), _Alignof(size_t),   nu_size_t,      np_size_t},
    {'q',       sizeof(long long), _Alignof(long long), nu_longlong, np_longlong},
    {'Q',       sizeof(long long), _Alignof(long long), nu_ulonglong,np_ulonglong},
    {'?',       sizeof(_Bool),      _Alignof(_Bool),     nu_bool,        np_bool},
    {'e',       sizeof(short),  _Alignof(short),    nu_halffloat,   np_halffloat},
    {'f',       sizeof(float),  _Alignof(float),    nu_float,       np_float},
    {'d',       sizeof(double), _Alignof(double),   nu_double,      np_double},
    {'F',       2*sizeof(float), _Alignof(float), nu_float_complex, np_float_complex},
    {'D',       2*sizeof(double), _Alignof(double), nu_double_complex, np_double_complex},
    {'P',       sizeof(void *), _Alignof(void *),   nu_void_p,      np_void_p},
    {0}
};

/* Big-endian routines. *****************************************************/

static PyObject *
bu_short(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long x = 0;

    /* This function is only ever used in the case f->size == 2. */
    assert(f->size == 2);
    Py_ssize_t i = 2;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | *bytes++;
    } while (--i > 0);
    /* Extend sign, avoiding implementation-defined or undefined behaviour. */
    x = (x ^ 0x8000U) - 0x8000U;
    return PyLong_FromLong(x & 0x8000U ? -1 - (long)(~x) : (long)x);
}

static PyObject *
bu_int(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long x = 0;

    /* This function is only ever used in the case f->size == 4. */
    assert(f->size == 4);
    Py_ssize_t i = 4;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | *bytes++;
    } while (--i > 0);
    /* Extend sign, avoiding implementation-defined or undefined behaviour. */
    x = (x ^ 0x80000000U) - 0x80000000U;
    return PyLong_FromLong(x & 0x80000000U ? -1 - (long)(~x) : (long)x);
}

static PyObject *
bu_uint(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long x = 0;
    Py_ssize_t i = f->size;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | *bytes++;
    } while (--i > 0);
    return PyLong_FromUnsignedLong(x);
}

static PyObject *
bu_longlong(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long long x = 0;

    /* This function is only ever used in the case f->size == 8. */
    assert(f->size == 8);
    Py_ssize_t i = 8;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | *bytes++;
    } while (--i > 0);
    /* Extend sign, avoiding implementation-defined or undefined behaviour. */
    x = (x ^ 0x8000000000000000U) - 0x8000000000000000U;
    return PyLong_FromLongLong(
        x & 0x8000000000000000U ? -1 - (long long)(~x) : (long long)x);
}

static PyObject *
bu_ulonglong(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long long x = 0;
    Py_ssize_t i = f->size;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | *bytes++;
    } while (--i > 0);
    return PyLong_FromUnsignedLongLong(x);
}

static PyObject *
bu_halffloat(_structmodulestate *state, const char *p, const formatdef *f)
{
    return unpack_halffloat(p, 0);
}

static PyObject *
bu_float(_structmodulestate *state, const char *p, const formatdef *f)
{
    return unpack_float(p, 0);
}

static PyObject *
bu_double(_structmodulestate *state, const char *p, const formatdef *f)
{
    return unpack_double(p, 0);
}

static PyObject *
bu_float_complex(_structmodulestate *state, const char *p, const formatdef *f)
{
    double x = PyFloat_Unpack4(p, 0);
    if (x == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    double y = PyFloat_Unpack4(p + 4, 0);
    if (y == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    return PyComplex_FromDoubles(x, y);
}

static PyObject *
bu_double_complex(_structmodulestate *state, const char *p, const formatdef *f)
{
    double x, y;

    x = PyFloat_Unpack8(p, 0);
    if (x == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    y = PyFloat_Unpack8(p + 8, 0);
    if (y == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    return PyComplex_FromDoubles(x, y);
}

static PyObject *
bu_bool(_structmodulestate *state, const char *p, const formatdef *f)
{
    return PyBool_FromLong(*p != 0);
}

static int
bp_int(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long x;
    Py_ssize_t i;
    unsigned char *q = (unsigned char *)p;
    if (get_long(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 0);
        }
        return -1;
    }
    i = f->size;
    if (i != SIZEOF_LONG) {
        if ((i == 2) && (x < -32768 || x > 32767))
            RANGE_ERROR(state, f, 0);
#if (SIZEOF_LONG != 4)
        else if ((i == 4) && (x < -2147483648L || x > 2147483647L))
            RANGE_ERROR(state, f, 0);
#endif
    }
    do {
        q[--i] = (unsigned char)(x & 0xffL);
        x >>= 8;
    } while (i > 0);
    return 0;
}

static int
bp_uint(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    unsigned long x;
    Py_ssize_t i;
    unsigned char *q = (unsigned char *)p;
    if (get_ulong(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 1);
        }
        return -1;
    }
    i = f->size;
    if (i != SIZEOF_LONG) {
        unsigned long maxint = 1;
        maxint <<= (unsigned long)(i * 8);
        if (x >= maxint)
            RANGE_ERROR(state, f, 1);
    }
    do {
        q[--i] = (unsigned char)(x & 0xffUL);
        x >>= 8;
    } while (i > 0);
    return 0;
}

static int
bp_longlong(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    int res;
    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    res = _PyLong_AsByteArray((PyLongObject *)v,
                              (unsigned char *)p,
                              8,
                              0, /* little_endian */
                              1, /* signed */
                              0  /* !with_exceptions */);
    Py_DECREF(v);
    if (res < 0) {
        PyErr_Format(state->StructError,
                     "'%c' format requires %lld <= number <= %lld",
                     f->format,
                     LLONG_MIN,
                     LLONG_MAX);
        return -1;
    }
    return res;
}

static int
bp_ulonglong(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    int res;
    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    res = _PyLong_AsByteArray((PyLongObject *)v,
                              (unsigned char *)p,
                              8,
                              0, /* little_endian */
                              0, /* signed */
                              0  /* !with_exceptions */);
    Py_DECREF(v);
    if (res < 0) {
        PyErr_Format(state->StructError,
                     "'%c' format requires 0 <= number <= %llu",
                     f->format,
                     ULLONG_MAX);
        return -1;
    }
    return res;
}

static int
bp_halffloat(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    return pack_halffloat(state, p, v, 0);
}

static int
bp_float(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    double x = PyFloat_AsDouble(v);
    if (x == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a float");
        return -1;
    }
    return PyFloat_Pack4(x, p, 0);
}

static int
bp_double(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    double x = PyFloat_AsDouble(v);
    if (x == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a float");
        return -1;
    }
    return PyFloat_Pack8(x, p, 0);
}

static int
bp_float_complex(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    Py_complex x = PyComplex_AsCComplex(v);
    if (x.real == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a complex");
        return -1;
    }
    if (PyFloat_Pack4(x.real, p, 0)) {
        return -1;
    }
    return PyFloat_Pack4(x.imag, p + 4, 0);
}

static int
bp_double_complex(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    Py_complex x = PyComplex_AsCComplex(v);
    if (x.real == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a complex");
        return -1;
    }
    if (PyFloat_Pack8(x.real, p, 0)) {
        return -1;
    }
    return PyFloat_Pack8(x.imag, p + 8, 0);
}

static int
bp_bool(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    int y;
    y = PyObject_IsTrue(v);
    if (y < 0)
        return -1;
    *p = (char)y;
    return 0;
}

static formatdef bigendian_table[] = {
    {'x',       1,              0,              NULL},
    {'b',       1,              0,              nu_byte,        np_byte},
    {'B',       1,              0,              nu_ubyte,       np_ubyte},
    {'c',       1,              0,              nu_char,        np_char},
    {'s',       1,              0,              NULL},
    {'p',       1,              0,              NULL},
    {'h',       2,              0,              bu_short,       bp_int},
    {'H',       2,              0,              bu_uint,        bp_uint},
    {'i',       4,              0,              bu_int,         bp_int},
    {'I',       4,              0,              bu_uint,        bp_uint},
    {'l',       4,              0,              bu_int,         bp_int},
    {'L',       4,              0,              bu_uint,        bp_uint},
    {'q',       8,              0,              bu_longlong,    bp_longlong},
    {'Q',       8,              0,              bu_ulonglong,   bp_ulonglong},
    {'?',       1,              0,              bu_bool,        bp_bool},
    {'e',       2,              0,              bu_halffloat,   bp_halffloat},
    {'f',       4,              0,              bu_float,       bp_float},
    {'d',       8,              0,              bu_double,      bp_double},
    {'F',       8,              0,              bu_float_complex, bp_float_complex},
    {'D',       16,             0,              bu_double_complex, bp_double_complex},
    {0}
};

/* Little-endian routines. *****************************************************/

static PyObject *
lu_short(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long x = 0;

    /* This function is only ever used in the case f->size == 2. */
    assert(f->size == 2);
    Py_ssize_t i = 2;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | bytes[--i];
    } while (i > 0);
    /* Extend sign, avoiding implementation-defined or undefined behaviour. */
    x = (x ^ 0x8000U) - 0x8000U;
    return PyLong_FromLong(x & 0x8000U ? -1 - (long)(~x) : (long)x);
}

static PyObject *
lu_int(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long x = 0;

    /* This function is only ever used in the case f->size == 4. */
    assert(f->size == 4);
    Py_ssize_t i = 4;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | bytes[--i];
    } while (i > 0);
    /* Extend sign, avoiding implementation-defined or undefined behaviour. */
    x = (x ^ 0x80000000U) - 0x80000000U;
    return PyLong_FromLong(x & 0x80000000U ? -1 - (long)(~x) : (long)x);
}

static PyObject *
lu_uint(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long x = 0;
    Py_ssize_t i = f->size;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | bytes[--i];
    } while (i > 0);
    return PyLong_FromUnsignedLong(x);
}

static PyObject *
lu_longlong(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long long x = 0;

    /* This function is only ever used in the case f->size == 8. */
    assert(f->size == 8);
    Py_ssize_t i = 8;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | bytes[--i];
    } while (i > 0);
    /* Extend sign, avoiding implementation-defined or undefined behaviour. */
    x = (x ^ 0x8000000000000000U) - 0x8000000000000000U;
    return PyLong_FromLongLong(
        x & 0x8000000000000000U ? -1 - (long long)(~x) : (long long)x);
}

static PyObject *
lu_ulonglong(_structmodulestate *state, const char *p, const formatdef *f)
{
    unsigned long long x = 0;
    Py_ssize_t i = f->size;
    const unsigned char *bytes = (const unsigned char *)p;
    do {
        x = (x<<8) | bytes[--i];
    } while (i > 0);
    return PyLong_FromUnsignedLongLong(x);
}

static PyObject *
lu_halffloat(_structmodulestate *state, const char *p, const formatdef *f)
{
    return unpack_halffloat(p, 1);
}

static PyObject *
lu_float(_structmodulestate *state, const char *p, const formatdef *f)
{
    return unpack_float(p, 1);
}

static PyObject *
lu_double(_structmodulestate *state, const char *p, const formatdef *f)
{
    return unpack_double(p, 1);
}

static PyObject *
lu_float_complex(_structmodulestate *state, const char *p, const formatdef *f)
{
    double x = PyFloat_Unpack4(p, 1);
    if (x == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    double y = PyFloat_Unpack4(p + 4, 1);
    if (y == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    return PyComplex_FromDoubles(x, y);
}

static PyObject *
lu_double_complex(_structmodulestate *state, const char *p, const formatdef *f)
{
    double x, y;

    x = PyFloat_Unpack8(p, 1);
    if (x == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    y = PyFloat_Unpack8(p + 8, 1);
    if (y == -1.0 && PyErr_Occurred()) {
        return NULL;
    }
    return PyComplex_FromDoubles(x, y);
}

static int
lp_int(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    long x;
    Py_ssize_t i;
    unsigned char *q = (unsigned char *)p;
    if (get_long(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 0);
        }
        return -1;
    }
    i = f->size;
    if (i != SIZEOF_LONG) {
        if ((i == 2) && (x < -32768 || x > 32767))
            RANGE_ERROR(state, f, 0);
#if (SIZEOF_LONG != 4)
        else if ((i == 4) && (x < -2147483648L || x > 2147483647L))
            RANGE_ERROR(state, f, 0);
#endif
    }
    do {
        *q++ = (unsigned char)(x & 0xffL);
        x >>= 8;
    } while (--i > 0);
    return 0;
}

static int
lp_uint(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    unsigned long x;
    Py_ssize_t i;
    unsigned char *q = (unsigned char *)p;
    if (get_ulong(state, v, &x) < 0) {
        if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
            RANGE_ERROR(state, f, 1);
        }
        return -1;
    }
    i = f->size;
    if (i != SIZEOF_LONG) {
        unsigned long maxint = 1;
        maxint <<= (unsigned long)(i * 8);
        if (x >= maxint)
            RANGE_ERROR(state, f, 1);
    }
    do {
        *q++ = (unsigned char)(x & 0xffUL);
        x >>= 8;
    } while (--i > 0);
    return 0;
}

static int
lp_longlong(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    int res;
    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    res = _PyLong_AsByteArray((PyLongObject*)v,
                              (unsigned char *)p,
                              8,
                              1, /* little_endian */
                              1, /* signed */
                              0  /* !with_exceptions */);
    Py_DECREF(v);
    if (res < 0) {
        PyErr_Format(state->StructError,
                     "'%c' format requires %lld <= number <= %lld",
                     f->format,
                     LLONG_MIN,
                     LLONG_MAX);
        return -1;
    }
    return res;
}

static int
lp_ulonglong(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    int res;
    v = get_pylong(state, v);
    if (v == NULL)
        return -1;
    res = _PyLong_AsByteArray((PyLongObject*)v,
                              (unsigned char *)p,
                              8,
                              1, /* little_endian */
                              0, /* signed */
                              0  /* !with_exceptions */);
    Py_DECREF(v);
    if (res < 0) {
        PyErr_Format(state->StructError,
                     "'%c' format requires 0 <= number <= %llu",
                     f->format,
                     ULLONG_MAX);
        return -1;
    }
    return res;
}

static int
lp_halffloat(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    return pack_halffloat(state, p, v, 1);
}

static int
lp_float(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    double x = PyFloat_AsDouble(v);
    if (x == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a float");
        return -1;
    }
    return PyFloat_Pack4(x, p, 1);
}

static int
lp_double(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    double x = PyFloat_AsDouble(v);
    if (x == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a float");
        return -1;
    }
    return PyFloat_Pack8(x, p, 1);
}

static int
lp_float_complex(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    Py_complex x = PyComplex_AsCComplex(v);
    if (x.real == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a complex");
        return -1;
    }
    if (PyFloat_Pack4(x.real, p, 1)) {
        return -1;
    }
    return PyFloat_Pack4(x.imag, p + 4, 1);

}

static int
lp_double_complex(_structmodulestate *state, char *p, PyObject *v, const formatdef *f)
{
    Py_complex x = PyComplex_AsCComplex(v);
    if (x.real == -1 && PyErr_Occurred()) {
        PyErr_SetString(state->StructError,
                        "required argument is not a complex");
        return -1;
    }
    if (PyFloat_Pack8(x.real, p, 1)) {
        return -1;
    }
    return PyFloat_Pack8(x.imag, p + 8, 1);
}

static formatdef lilendian_table[] = {
    {'x',       1,              0,              NULL},
    {'b',       1,              0,              nu_byte,        np_byte},
    {'B',       1,              0,              nu_ubyte,       np_ubyte},
    {'c',       1,              0,              nu_char,        np_char},
    {'s',       1,              0,              NULL},
    {'p',       1,              0,              NULL},
    {'h',       2,              0,              lu_short,       lp_int},
    {'H',       2,              0,              lu_uint,        lp_uint},
    {'i',       4,              0,              lu_int,         lp_int},
    {'I',       4,              0,              lu_uint,        lp_uint},
    {'l',       4,              0,              lu_int,         lp_int},
    {'L',       4,              0,              lu_uint,        lp_uint},
    {'q',       8,              0,              lu_longlong,    lp_longlong},
    {'Q',       8,              0,              lu_ulonglong,   lp_ulonglong},
    {'?',       1,              0,              bu_bool,        bp_bool}, /* Std rep not endian dep,
        but potentially different from native rep -- reuse bx_bool funcs. */
    {'e',       2,              0,              lu_halffloat,   lp_halffloat},
    {'f',       4,              0,              lu_float,       lp_float},
    {'d',       8,              0,              lu_double,      lp_double},
    {'F',       8,              0,              lu_float_complex, lp_float_complex},
    {'D',       16,             0,              lu_double_complex, lp_double_complex},
    {0}
};

/* Ensure endian table optimization happens exactly once across all interpreters */
static _PyOnceFlag endian_tables_init_once = {0};

static int
init_endian_tables(void *Py_UNUSED(arg))
{
    const formatdef *native = native_table;
    formatdef *other, *ptr;
#if PY_LITTLE_ENDIAN
    other = lilendian_table;
#else
    other = bigendian_table;
#endif
    /* Scan through the native table, find a matching
        entry in the endian table and swap in the
        native implementations whenever possible
        (64-bit platforms may not have "standard" sizes) */
    while (native->format != '\0' && other->format != '\0') {
        ptr = other;
        while (ptr->format != '\0') {
            if (ptr->format == native->format) {
                /* Match faster when formats are
                    listed in the same order */
                if (ptr == other)
                    other++;
                /* Only use the trick if the
                    size matches */
                if (ptr->size != native->size)
                    break;
                /* Skip _Bool, semantics are different for standard size */
                if (ptr->format == '?')
                    break;
                ptr->pack = native->pack;
                ptr->unpack = native->unpack;
                break;
            }
            ptr++;
        }
        native++;
    }
    return 0;
}


static const formatdef *
whichtable(const char **pfmt)
{
    const char *fmt = (*pfmt)++; /* May be backed out of later */
    switch (*fmt) {
    case '<':
        return lilendian_table;
    case '>':
    case '!': /* Network byte order is big-endian */
        return bigendian_table;
    case '=': { /* Host byte order -- different from native in alignment! */
#if PY_LITTLE_ENDIAN
        return lilendian_table;
#else
        return bigendian_table;
#endif
    }
    default:
        --*pfmt; /* Back out of pointer increment */
        _Py_FALLTHROUGH;
    case '@':
        return native_table;
    }
}


/* Get the table entry for a format code */

static const formatdef *
getentry(_structmodulestate *state, int c, const formatdef *f)
{
    for (; f->format != '\0'; f++) {
        if (f->format == c) {
            return f;
        }
    }
    PyErr_SetString(state->StructError, "bad char in struct format");
    return NULL;
}


/* Align a size according to a format code.  Return -1 on overflow. */

static Py_ssize_t
align(Py_ssize_t size, char c, const formatdef *e)
{
    Py_ssize_t extra;

    if (e->format == c) {
        if (e->alignment && size > 0) {
            extra = (e->alignment - 1) - (size - 1) % (e->alignment);
            if (extra > PY_SSIZE_T_MAX - size)
                return -1;
            size += extra;
        }
    }
    return size;
}

/*
 * Struct object implementation.
 */

/* calculate the size of a format string */

static int
prepare_s(PyStructObject *self, PyObject *format)
{
    const formatdef *f;
    const formatdef *e;
    formatcode *codes, *codes0;

    const char *s;
    const char *fmt;
    char c;
    Py_ssize_t size, len, num, itemsize;
    size_t ncodes;

    _structmodulestate *state = get_struct_state_structinst(self);

    if (!PyUnicode_IS_ASCII(format)) {
        PyErr_SetString(PyExc_ValueError, "non-ASCII character in struct format");
        return -1;
    }
    fmt = (const char *)PyUnicode_1BYTE_DATA(format);
    if (strlen(fmt) != (size_t)PyUnicode_GET_LENGTH(format)) {
        PyErr_SetString(state->StructError,
                        "embedded null character");
        return -1;
    }

    f = whichtable(&fmt);

    s = fmt;
    size = 0;
    len = 0;
    ncodes = 0;
    while ((c = *s++) != '\0') {
        if (Py_ISSPACE(c))
            continue;
        if ('0' <= c && c <= '9') {
            num = c - '0';
            while ('0' <= (c = *s++) && c <= '9') {
                /* overflow-safe version of
                   if (num*10 + (c - '0') > PY_SSIZE_T_MAX) { ... } */
                if (num >= PY_SSIZE_T_MAX / 10 && (
                        num > PY_SSIZE_T_MAX / 10 ||
                        (c - '0') > PY_SSIZE_T_MAX % 10))
                    goto overflow;
                num = num*10 + (c - '0');
            }
            if (c == '\0') {
                PyErr_SetString(state->StructError,
                                "repeat count given without format specifier");
                return -1;
            }
        }
        else
            num = 1;

        e = getentry(state, c, f);
        if (e == NULL)
            return -1;

        switch (c) {
            case 's': _Py_FALLTHROUGH;
            case 'p':
                if (len == PY_SSIZE_T_MAX) {
                    goto overflow;
                }
                len++;
                ncodes++;
                break;
            case 'x': break;
            default:
                if (num > PY_SSIZE_T_MAX - len) {
                    goto overflow;
                }
                len += num;
                if (num) {
                    ncodes++;
                }
                break;
        }

        itemsize = e->size;
        size = align(size, c, e);
        if (size == -1)
            goto overflow;

        /* if (size + num * itemsize > PY_SSIZE_T_MAX) { ... } */
        if (num > (PY_SSIZE_T_MAX - size) / itemsize)
            goto overflow;
        size += num * itemsize;
    }

    /* check for overflow */
    if ((ncodes + 1) > ((size_t)PY_SSIZE_T_MAX / sizeof(formatcode))) {
        PyErr_NoMemory();
        return -1;
    }

    codes = PyMem_Malloc((ncodes + 1) * sizeof(formatcode));
    if (codes == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    codes0 = codes;
    s = fmt;
    size = 0;
    while ((c = *s++) != '\0') {
        if (Py_ISSPACE(c))
            continue;
        if ('0' <= c && c <= '9') {
            num = c - '0';
            while ('0' <= (c = *s++) && c <= '9')
                num = num*10 + (c - '0');
        }
        else
            num = 1;

        e = getentry(state, c, f);

        size = align(size, c, e);
        if (c == 's' || c == 'p') {
            codes->offset = size;
            codes->size = num;
            codes->fmtdef = e;
            codes->repeat = 1;
            codes++;
            size += num;
        } else if (c == 'x') {
            size += num;
        } else if (num) {
            codes->offset = size;
            codes->size = e->size;
            codes->fmtdef = e;
            codes->repeat = num;
            codes++;
            size += e->size * num;
        }
    }
    codes->fmtdef = NULL;
    codes->offset = size;
    codes->size = 0;
    codes->repeat = 0;

    /* Free any s_codes value left over from a previous initialization. */
    if (self->s_codes != NULL)
        PyMem_Free(self->s_codes);
    self->s_codes = codes0;
    self->s_size = size;
    self->s_len = len;
    Py_XSETREF(self->s_format, Py_NewRef(format));

    return 0;

  overflow:
    PyErr_SetString(state->StructError,
                    "total struct size too long");
    return -1;
}

/* This should be moved to Struct_impl() when Struct___init__() and
 * s_new() will be removed (see gh-143715 and gh-94532). */
static int
set_format(PyStructObject *self, PyObject *format)
{
    if (PyUnicode_Check(format)) {
        format = PyUnicode_FromObject(format);
    }
    else if (PyBytes_Check(format)) {
        format = PyUnicode_DecodeASCII(PyBytes_AS_STRING(format),
                                       PyBytes_GET_SIZE(format), "surrogateescape");
    }
    else  {
        PyErr_Format(PyExc_TypeError,
                     "Struct() argument 1 must be a str or bytes object, "
                     "not %T", format);
        return -1;
    }
    if (format == NULL) {
        return -1;
    }
    if (prepare_s(self, format)) {
        Py_DECREF(format);
        return -1;
    }
    Py_DECREF(format);
    return 0;
}

/*[clinic input]
@classmethod
Struct.__new__

   format: object

Create a compiled struct object.

Return a new Struct object which writes and reads binary data according
to the format string.  See help(struct) for more on format strings.
[clinic start generated code]*/

static PyObject *
Struct_impl(PyTypeObject *type, PyObject *format)
/*[clinic end generated code: output=49468b044e334308 input=8381a9796f20f24e]*/
{
    PyStructObject *self = (PyStructObject *)type->tp_alloc(type, 0);
    if (self == NULL) {
        return NULL;
    }
    self->s_format = NULL;
    self->s_codes = NULL;
    self->s_size = -1;
    self->s_len = -1;
    self->init_called = false;
    if (set_format(self, format) < 0) {
        Py_DECREF(self);
        return NULL;
    }
    return (PyObject *)self;
}


static int
s_init(PyObject *self, PyObject *args, PyObject *kwargs);

static PyObject *
s_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    if (type->tp_new != s_new) {
        /* Struct.__new__() was called explicitly in a subclass' __new__(). */
        return Struct(type, args, kwds);
    }

    PyObject *format = NULL;
    if (PyTuple_GET_SIZE(args) == 1 && (kwds == NULL || PyDict_GET_SIZE(kwds) == 0)) {
        format = Py_NewRef(PyTuple_GET_ITEM(args, 0));
    }
    else if (PyTuple_GET_SIZE(args) == 0 && kwds != NULL && PyDict_GET_SIZE(kwds) == 1) {
        if (PyDict_GetItemStringRef(kwds, "format", &format) < 0) {
            return NULL;
        }
    }
    if (format == NULL && type->tp_init != s_init) {
        Py_ssize_t nargs = PyTuple_GET_SIZE(args) + (kwds ? PyDict_GET_SIZE(kwds) : 0);
        if (nargs > 1) {
            if (PyErr_WarnFormat(PyExc_DeprecationWarning, 1,
                "Struct() takes at most 1 argument (%zd given)", nargs))
            {
                Py_XDECREF(format);
                return NULL;
            }
        }
        else {
            if (PyErr_WarnEx(PyExc_DeprecationWarning,
                "Struct() missing required argument 'format' (pos 1)", 1))
            {
                Py_XDECREF(format);
                return NULL;
            }
        }
    }

    PyStructObject *self = (PyStructObject *)type->tp_alloc(type, 0);
    if (self == NULL) {
        return NULL;
    }
    self->s_format = NULL;
    self->s_codes = NULL;
    self->s_size = -1;
    self->s_len = -1;
    self->init_called = false;
    if (format && set_format(self, format) < 0) {
        if (type->tp_init == s_init) {
            /* No custom __init__() method, so __new__() should do
             * all the work. */
            Py_DECREF(format);
            Py_DECREF(self);
            return NULL;
        }
        PyObject *exc = PyErr_GetRaisedException();
        Py_CLEAR(self->s_format);
        if (PyErr_WarnFormat(PyExc_DeprecationWarning, 1,
            "Invalid 'format' argument for Struct.__new__(): %S", exc))
        {
            Py_DECREF(exc);
            Py_DECREF(format);
            Py_DECREF(self);
            return NULL;
        }
        Py_DECREF(exc);
    }
    Py_XDECREF(format);
    return (PyObject *)self;
}

static bool
same_format(PyStructObject *s, PyObject *format)
{
    Py_ssize_t size = PyUnicode_GET_LENGTH(s->s_format);
    const void *data = PyUnicode_1BYTE_DATA(s->s_format);
    if (PyUnicode_Check(format) && PyUnicode_IS_ASCII(format)) {
        return PyUnicode_GET_LENGTH(format) == size
            && memcmp(PyUnicode_1BYTE_DATA(format), data, size) == 0;
    }
    if (PyBytes_Check(format)) {
        return PyBytes_GET_SIZE(format) == size
            && memcmp(PyBytes_AS_STRING(format), data, size) == 0;
    }
    return false;
}

/*[clinic input]
Struct.__init__

    format: object

Create a compiled struct object.

Return a new Struct object which writes and reads binary data according
to the format string.  See help(struct) for more on format strings.
[clinic start generated code]*/

static int
Struct___init___impl(PyStructObject *self, PyObject *format)
/*[clinic end generated code: output=b8e80862444e92d0 input=1af78a5f57d82cec]*/
{
    if (self->s_format == NULL) {
        if (set_format(self, format) < 0) {
            return -1;
        }
    }
    else if (!same_format(self, format)) {
        const char *msg = self->init_called
            ? "Re-initialization of Struct by calling the __init__() method "
              "will not work in future Python versions"
            : "Different format arguments for __new__() and __init__() "
              "methods of Struct";
        if (PyErr_WarnEx(PyExc_FutureWarning, msg, 1)) {
            return -1;
        }
        if (set_format(self, format) < 0) {
            return -1;
        }
    }
    self->init_called = true;
    return 0;
}

static int
s_init(PyObject *self, PyObject *args, PyObject *kwargs)
{
    if (!((PyStructObject *)self)->init_called
            && Py_TYPE(self)->tp_init == s_init
            && ((PyStructObject *)self)->s_format != NULL)
    {
        /* Struct.__init__() was called implicitly.
         * __new__() already did all the work. */
        ((PyStructObject *)self)->init_called = true;
        return 0;
    }
    /* Struct.__init__() was called explicitly. */
    return Struct___init__(self, args, kwargs);
}

static int
s_clear(PyObject *op)
{
    PyStructObject *s = PyStructObject_CAST(op);
    Py_CLEAR(s->s_format);
    return 0;
}

static int
s_traverse(PyObject *op, visitproc visit, void *arg)
{
    PyStructObject *s = PyStructObject_CAST(op);
    Py_VISIT(Py_TYPE(s));
    Py_VISIT(s->s_format);
    return 0;
}

static void
s_dealloc(PyObject *op)
{
    PyStructObject *s = PyStructObject_CAST(op);
    PyTypeObject *tp = Py_TYPE(s);
    PyObject_GC_UnTrack(s);
    FT_CLEAR_WEAKREFS(op, s->weakreflist);
    if (s->s_codes != NULL) {
        PyMem_Free(s->s_codes);
    }
    Py_XDECREF(s->s_format);
    tp->tp_free(s);
    Py_DECREF(tp);
}

static PyObject *
s_unpack_internal(PyStructObject *soself, const char *startfrom,
                  _structmodulestate *state) {
    formatcode *code;
    Py_ssize_t i = 0;
    PyObject *result = PyTuple_New(soself->s_len);
    if (result == NULL)
        return NULL;

    for (code = soself->s_codes; code->fmtdef != NULL; code++) {
        const formatdef *e = code->fmtdef;
        const char *res = startfrom + code->offset;
        Py_ssize_t j = code->repeat;
        while (j--) {
            PyObject *v;
            if (e->format == 's') {
                v = PyBytes_FromStringAndSize(res, code->size);
            } else if (e->format == 'p') {
                Py_ssize_t n;
                if (code->size == 0) {
                    n = 0;
                }
                else {
                    n = *(unsigned char*)res;
                    if (n >= code->size) {
                        n = code->size - 1;
                    }
                }
                v = PyBytes_FromStringAndSize(res + 1, n);
            } else {
                v = e->unpack(state, res, e);
            }
            if (v == NULL)
                goto fail;
            PyTuple_SET_ITEM(result, i++, v);
            res += code->size;
        }
    }

    return result;
fail:
    Py_DECREF(result);
    return NULL;
}

#define ENSURE_STRUCT_IS_READY(self)                             \
    do {                                                         \
        if (!(self)->s_codes) {                                  \
            PyErr_SetString(PyExc_RuntimeError,                  \
                            "Struct object is not initialized"); \
            return NULL;                                         \
        }                                                        \
    } while (0);

/*[clinic input]
Struct.unpack

    buffer: Py_buffer
    /

Return a tuple containing unpacked values.

Unpack according to the struct format string.  The buffer's
size in bytes must be the struct size.  See help(struct) for more on
format strings.
[clinic start generated code]*/

static PyObject *
Struct_unpack_impl(PyStructObject *self, Py_buffer *buffer)
/*[clinic end generated code: output=873a24faf02e848a input=488843a57c47065a]*/
{
    _structmodulestate *state = get_struct_state_structinst(self);
    ENSURE_STRUCT_IS_READY(self);
    if (buffer->len != self->s_size) {
        PyErr_Format(state->StructError,
                     "unpack requires a buffer of %zd bytes",
                     self->s_size);
        return NULL;
    }
    return s_unpack_internal(self, buffer->buf, state);
}

/*[clinic input]
Struct.unpack_from

    buffer: Py_buffer
    offset: Py_ssize_t = 0

Return a tuple containing unpacked values.

Values are unpacked according to the struct format string.  The
buffer's size in bytes, starting at position offset, must be at
least the struct size.  See help(struct) for more on format
strings.
[clinic start generated code]*/

static PyObject *
Struct_unpack_from_impl(PyStructObject *self, Py_buffer *buffer,
                        Py_ssize_t offset)
/*[clinic end generated code: output=57fac875e0977316 input=57cfcf84c088faa4]*/
{
    _structmodulestate *state = get_struct_state_structinst(self);
    ENSURE_STRUCT_IS_READY(self);

    if (offset < 0) {
        if (offset + self->s_size > 0) {
            PyErr_Format(state->StructError,
                         "not enough data to unpack %zd bytes at offset %zd",
                         self->s_size,
                         offset);
            return NULL;
        }

        if (offset + buffer->len < 0) {
            PyErr_Format(state->StructError,
                         "offset %zd out of range for %zd-byte buffer",
                         offset,
                         buffer->len);
            return NULL;
        }
        offset += buffer->len;
    }

    if ((buffer->len - offset) < self->s_size) {
        PyErr_Format(state->StructError,
                     "unpack_from requires a buffer of at least %zu bytes for "
                     "unpacking %zd bytes at offset %zd "
                     "(actual buffer size is %zd)",
                     (size_t)self->s_size + (size_t)offset,
                     self->s_size,
                     offset,
                     buffer->len);
        return NULL;
    }
    return s_unpack_internal(self, (char*)buffer->buf + offset, state);
}


/* Unpack iterator type */

typedef struct {
    PyObject_HEAD
    PyStructObject *so;
    Py_buffer buf;
    Py_ssize_t index;
} unpackiterobject;

#define unpackiterobject_CAST(op)   ((unpackiterobject *)(op))

static void
unpackiter_dealloc(PyObject *op)
{
    unpackiterobject *self = unpackiterobject_CAST(op);
    /* bpo-31095: UnTrack is needed before calling any callbacks */
    PyTypeObject *tp = Py_TYPE(self);
    PyObject_GC_UnTrack(self);
    Py_XDECREF(self->so);
    PyBuffer_Release(&self->buf);
    PyObject_GC_Del(self);
    Py_DECREF(tp);
}

static int
unpackiter_traverse(PyObject *op, visitproc visit, void *arg)
{
    unpackiterobject *self = unpackiterobject_CAST(op);
    Py_VISIT(Py_TYPE(self));
    Py_VISIT(self->so);
    Py_VISIT(self->buf.obj);
    return 0;
}

static PyObject *
unpackiter_len(PyObject *op, PyObject *Py_UNUSED(dummy))
{
    Py_ssize_t len;
    unpackiterobject *self = unpackiterobject_CAST(op);
    if (self->so == NULL) {
        len = 0;
    }
    else {
        len = (self->buf.len - self->index) / self->so->s_size;
    }
    return PyLong_FromSsize_t(len);
}

static PyMethodDef unpackiter_methods[] = {
    {"__length_hint__", unpackiter_len, METH_NOARGS, NULL},
    {NULL,              NULL}           /* sentinel */
};

static PyObject *
unpackiter_iternext(PyObject *op)
{
    unpackiterobject *self = unpackiterobject_CAST(op);
    _structmodulestate *state = get_struct_state_iterinst(self);
    PyObject *result;
    if (self->so == NULL) {
        return NULL;
    }
    if (self->index >= self->buf.len) {
        /* Iterator exhausted */
        Py_CLEAR(self->so);
        PyBuffer_Release(&self->buf);
        return NULL;
    }
    assert(self->index + self->so->s_size <= self->buf.len);
    result = s_unpack_internal(self->so,
                               (char*)self->buf.buf + self->index,
                               state);
    self->index += self->so->s_size;
    return result;
}

static PyType_Slot unpackiter_type_slots[] = {
    {Py_tp_dealloc, unpackiter_dealloc},
    {Py_tp_getattro, PyObject_GenericGetAttr},
    {Py_tp_traverse, unpackiter_traverse},
    {Py_tp_iter, PyObject_SelfIter},
    {Py_tp_iternext, unpackiter_iternext},
    {Py_tp_methods, unpackiter_methods},
    {0, 0},
};

static PyType_Spec unpackiter_type_spec = {
    "_struct.unpack_iterator",
    sizeof(unpackiterobject),
    0,
    (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     Py_TPFLAGS_IMMUTABLETYPE | Py_TPFLAGS_DISALLOW_INSTANTIATION),
    unpackiter_type_slots
};

/*[clinic input]
Struct.iter_unpack

    buffer: object
    /

Return an iterator yielding tuples.

Tuples are unpacked from the given bytes source, like a repeated
invocation of unpack_from().  Requires that the bytes length be
a multiple of the struct size.
[clinic start generated code]*/

static PyObject *
Struct_iter_unpack_impl(PyStructObject *self, PyObject *buffer)
/*[clinic end generated code: output=818f89ad4afa8d64 input=9555d2d29d1d9cd2]*/
{
    _structmodulestate *state = get_struct_state_structinst(self);
    unpackiterobject *iter;
    ENSURE_STRUCT_IS_READY(self);

    if (self->s_size == 0) {
        PyErr_Format(state->StructError,
                     "cannot iteratively unpack with a struct of length 0");
        return NULL;
    }

    iter = (unpackiterobject *) PyType_GenericAlloc((PyTypeObject *)state->unpackiter_type, 0);
    if (iter == NULL)
        return NULL;

    if (PyObject_GetBuffer(buffer, &iter->buf, PyBUF_SIMPLE) < 0) {
        Py_DECREF(iter);
        return NULL;
    }
    if (iter->buf.len % self->s_size != 0) {
        PyErr_Format(state->StructError,
                     "iterative unpacking requires a buffer of "
                     "a multiple of %zd bytes",
                     self->s_size);
        Py_DECREF(iter);
        return NULL;
    }
    iter->so = (PyStructObject*)Py_NewRef(self);
    iter->index = 0;
    return (PyObject *)iter;
}


/*
 * Guts of the pack function.
 *
 * Takes a struct object, a tuple of arguments, and offset in that tuple of
 * argument for where to start processing the arguments for packing, and a
 * character buffer for writing the packed string.  The caller must insure
 * that the buffer may contain the required length for packing the arguments.
 * 0 is returned on success, 1 is returned if there is an error.
 *
 */
static int
s_pack_internal(PyStructObject *soself, PyObject *const *args,
                char* buf, _structmodulestate *state)
{
    formatcode *code;
    /* XXX(nnorwitz): why does i need to be a local?  can we use
       the offset parameter or do we need the wider width? */
    Py_ssize_t i;

    memset(buf, '\0', soself->s_size);
    i = 0;
    for (code = soself->s_codes; code->fmtdef != NULL; code++) {
        const formatdef *e = code->fmtdef;
        char *res = buf + code->offset;
        Py_ssize_t j = code->repeat;
        while (j--) {
            PyObject *v = args[i++];
            if (e->format == 's') {
                Py_ssize_t n;
                int isstring;
                const void *p;
                isstring = PyBytes_Check(v);
                if (!isstring && !PyByteArray_Check(v)) {
                    PyErr_SetString(state->StructError,
                                    "argument for 's' must be a bytes object");
                    return -1;
                }
                if (isstring) {
                    n = PyBytes_GET_SIZE(v);
                    p = PyBytes_AS_STRING(v);
                }
                else {
                    n = PyByteArray_GET_SIZE(v);
                    p = PyByteArray_AS_STRING(v);
                }
                if (n > code->size)
                    n = code->size;
                if (n > 0)
                    memcpy(res, p, n);
            } else if (e->format == 'p') {
                Py_ssize_t n;
                int isstring;
                const void *p;
                isstring = PyBytes_Check(v);
                if (!isstring && !PyByteArray_Check(v)) {
                    PyErr_SetString(state->StructError,
                                    "argument for 'p' must be a bytes object");
                    return -1;
                }
                if (isstring) {
                    n = PyBytes_GET_SIZE(v);
                    p = PyBytes_AS_STRING(v);
                }
                else {
                    n = PyByteArray_GET_SIZE(v);
                    p = PyByteArray_AS_STRING(v);
                }
                if (code->size == 0) {
                    n = 0;
                }
                else if (n > (code->size - 1)) {
                    n = code->size - 1;
                }
                if (n > 0)
                    memcpy(res + 1, p, n);
                if (n > 255)
                    n = 255;
                *res = Py_SAFE_DOWNCAST(n, Py_ssize_t, unsigned char);
            } else {
                if (e->pack(state, res, v, e) < 0) {
                    if (PyLong_Check(v) && PyErr_ExceptionMatches(PyExc_OverflowError))
                        PyErr_SetString(state->StructError,
                                        "int too large to convert");
                    return -1;
                }
            }
            res += code->size;
        }
    }

    /* Success */
    return 0;
}


/*[clinic input]
Struct.pack

    *values: array

Pack values and return the packed bytes.

Return a bytes object containing the provided values packed
according to the struct format string.  See help(struct) for more on
format strings.
[clinic start generated code]*/

static PyObject *
Struct_pack_impl(PyStructObject *self, PyObject * const *values,
                 Py_ssize_t values_length)
/*[clinic end generated code: output=5766e18f596cae9e input=295f4b1a97747458]*/
{
    _structmodulestate *state = get_struct_state_structinst(self);

    /* Validate arguments. */
    ENSURE_STRUCT_IS_READY(self);
    if (values_length != self->s_len) {
        PyErr_Format(state->StructError,
                     "pack expected %zd items for packing (got %zd)",
                     self->s_len, values_length);
        return NULL;
    }

    PyBytesWriter *writer = PyBytesWriter_Create(self->s_size);
    if (writer == NULL) {
        return NULL;
    }
    char *buf = PyBytesWriter_GetData(writer);

    /* Call the guts */
    if (s_pack_internal(self, values, buf, state) != 0) {
        PyBytesWriter_Discard(writer);
        return NULL;
    }

    return PyBytesWriter_FinishWithSize(writer, self->s_size);
}

/*[clinic input]
Struct.pack_into

    buffer: Py_buffer(accept={rwbuffer})
    offset: Py_ssize_t
    /
    *values: array

Pack values and write the packed bytes into the buffer.

Pack the provided values according to the struct format string
and write the packed bytes into the writable buffer starting at
offset.  Note that the offset is a required argument.  See
help(struct) for more on format strings.
[clinic start generated code]*/

static PyObject *
Struct_pack_into_impl(PyStructObject *self, Py_buffer *buffer,
                      Py_ssize_t offset, PyObject * const *values,
                      Py_ssize_t values_length)
/*[clinic end generated code: output=aa9d9a93f5f8f77b input=9d842a368ee14245]*/
{
    _structmodulestate *state = get_struct_state_structinst(self);

    ENSURE_STRUCT_IS_READY(self);
    if (values_length != self->s_len) {
        PyErr_Format(state->StructError,
                     "pack_into expected %zd items for packing (got %zd)",
                     self->s_len, values_length);
        return NULL;
    }

    /* Support negative offsets. */
    if (offset < 0) {
         /* Check that negative offset is low enough to fit data */
        if (offset + self->s_size > 0) {
            PyErr_Format(state->StructError,
                         "no space to pack %zd bytes at offset %zd",
                         self->s_size,
                         offset);
            return NULL;
        }

        /* Check that negative offset is not crossing buffer boundary */
        if (offset + buffer->len < 0) {
            PyErr_Format(state->StructError,
                         "offset %zd out of range for %zd-byte buffer",
                         offset,
                         buffer->len);
            return NULL;
        }

        offset += buffer->len;
    }

    /* Check boundaries */
    if ((buffer->len - offset) < self->s_size) {
        assert(offset >= 0);
        assert(self->s_size >= 0);

        PyErr_Format(state->StructError,
                     "pack_into requires a buffer of at least %zu bytes for "
                     "packing %zd bytes at offset %zd "
                     "(actual buffer size is %zd)",
                     (size_t)self->s_size + (size_t)offset,
                     self->s_size,
                     offset,
                     buffer->len);
        return NULL;
    }

    /* Call the guts */
    if (s_pack_internal(self, values, (char*)buffer->buf + offset, state) != 0) {
        return NULL;
    }

    Py_RETURN_NONE;
}

/*[clinic input]
Struct.__sizeof__
[clinic start generated code]*/

static PyObject *
Struct___sizeof___impl(PyStructObject *self)
/*[clinic end generated code: output=2d0d78900b4cdb4e input=faca5925c1f1ffd0]*/
{
    ENSURE_STRUCT_IS_READY(self);
    size_t size = _PyObject_SIZE(Py_TYPE(self)) + sizeof(formatcode);
    for (formatcode *code = self->s_codes; code->fmtdef != NULL; code++) {
        size += sizeof(formatcode);
    }
    return PyLong_FromSize_t(size);
}

static PyObject *
s_repr(PyObject *op)
{
    PyStructObject *self = PyStructObject_CAST(op);
    ENSURE_STRUCT_IS_READY(self);
    return PyUnicode_FromFormat("%s(%R)", _PyType_Name(Py_TYPE(self)), self->s_format);
}

/* List of functions */

static struct PyMethodDef s_methods[] = {
    STRUCT_ITER_UNPACK_METHODDEF
    STRUCT_PACK_METHODDEF
    STRUCT_PACK_INTO_METHODDEF
    STRUCT_UNPACK_METHODDEF
    STRUCT_UNPACK_FROM_METHODDEF
    STRUCT___SIZEOF___METHODDEF
    {NULL,       NULL}          /* sentinel */
};

static PyMemberDef s_members[] = {
    {"__weaklistoffset__", Py_T_PYSSIZET, offsetof(PyStructObject, weakreflist), Py_READONLY},
    {"format", Py_T_OBJECT_EX, offsetof(PyStructObject, s_format),
        Py_READONLY, PyDoc_STR("struct format string")},
    {"size", Py_T_PYSSIZET, offsetof(PyStructObject, s_size), Py_READONLY,
        PyDoc_STR("struct size in bytes")},
    {NULL}  /* sentinel */
};

static PyType_Slot PyStructType_slots[] = {
    {Py_tp_dealloc, s_dealloc},
    {Py_tp_getattro, PyObject_GenericGetAttr},
    {Py_tp_setattro, PyObject_GenericSetAttr},
    {Py_tp_repr, s_repr},
    {Py_tp_doc, (void*)Struct___init____doc__},
    {Py_tp_traverse, s_traverse},
    {Py_tp_clear, s_clear},
    {Py_tp_methods, s_methods},
    {Py_tp_members, s_members},
    {Py_tp_init, s_init},
    {Py_tp_new, s_new},
    {0, 0},
};

static PyType_Spec PyStructType_spec = {
    "_struct.Struct",
    sizeof(PyStructObject),
    0,
    (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     Py_TPFLAGS_BASETYPE | Py_TPFLAGS_IMMUTABLETYPE),
    PyStructType_slots
};


/* ---- Standalone functions  ---- */

#define MAXCACHE 100

static int
cache_struct_converter(PyObject *module, PyObject *fmt, PyStructObject **ptr)
{
    PyObject * s_object;
    _structmodulestate *state = get_struct_state(module);

    if (fmt == NULL) {
        Py_SETREF(*ptr, NULL);
        return 1;
    }

    if (PyDict_GetItemRef(state->cache, fmt, &s_object) < 0) {
        return 0;
    }
    if (s_object != NULL) {
        *ptr = PyStructObject_CAST(s_object);
        return Py_CLEANUP_SUPPORTED;
    }

    s_object = PyObject_CallOneArg(state->PyStructType, fmt);
    if (s_object != NULL) {
        if (PyDict_GET_SIZE(state->cache) >= MAXCACHE)
            PyDict_Clear(state->cache);
        /* Attempt to cache the result */
        if (PyDict_SetItem(state->cache, fmt, s_object) == -1)
            PyErr_Clear();
        *ptr = (PyStructObject *)s_object;
        return Py_CLEANUP_SUPPORTED;
    }
    return 0;
}

/*[clinic input]
_clearcache

Clear the internal cache.
[clinic start generated code]*/

static PyObject *
_clearcache_impl(PyObject *module)
/*[clinic end generated code: output=ce4fb8a7bf7cb523 input=463eaae04bab3211]*/
{
    PyDict_Clear(get_struct_state(module)->cache);
    Py_RETURN_NONE;
}


/*[clinic input]
calcsize -> Py_ssize_t

    format as s_object: cache_struct
    /

Return size in bytes of the struct described by the format string.
[clinic start generated code]*/

static Py_ssize_t
calcsize_impl(PyObject *module, PyStructObject *s_object)
/*[clinic end generated code: output=db7d23d09c6932c4 input=96a6a590c7717ecd]*/
{
    return s_object->s_size;
}

/*[clinic input]
pack

    format as s_object: cache_struct
    /
    *values: array

Pack values and return the packed bytes.

Return a bytes object containing the provided values packed according
to the format string.  See help(struct) for more on format strings.
[clinic start generated code]*/

static PyObject *
pack_impl(PyObject *module, PyStructObject *s_object,
          PyObject * const *values, Py_ssize_t values_length)
/*[clinic end generated code: output=2f874191ddecdec0 input=8144972342391de1]*/
{
    return Struct_pack_impl(s_object, values, values_length);
}

/*[clinic input]
pack_into

    format as s_object: cache_struct
    buffer: Py_buffer(accept={rwbuffer})
    offset: Py_ssize_t
    /
    *values: array

Pack values and write the packed bytes into the buffer.

Pack the provided values according to the format string and write the
packed bytes into the writable buffer starting at offset.  Note that the
offset is a required argument.  See help(struct) for more on format
strings.
[clinic start generated code]*/

static PyObject *
pack_into_impl(PyObject *module, PyStructObject *s_object, Py_buffer *buffer,
               Py_ssize_t offset, PyObject * const *values,
               Py_ssize_t values_length)
/*[clinic end generated code: output=e8bf7d422b2088ef input=086867c0f5d8a8e4]*/
{
    return Struct_pack_into_impl(s_object, buffer, offset,
                                 values, values_length);
}

/*[clinic input]
unpack

    format as s_object: cache_struct
    buffer: Py_buffer
    /

Return a tuple containing values unpacked according to the format string.

The buffer's size in bytes must be calcsize(format).  See help(struct)
for more on format strings.
[clinic start generated code]*/

static PyObject *
unpack_impl(PyObject *module, PyStructObject *s_object, Py_buffer *buffer)
/*[clinic end generated code: output=48ddd4d88eca8551 input=7df28c5d0b5b6f4e]*/
{
    return Struct_unpack_impl(s_object, buffer);
}

/*[clinic input]
unpack_from

    format as s_object: cache_struct
    /
    buffer: Py_buffer
    offset: Py_ssize_t = 0

Return a tuple containing values unpacked according to the format string.

The buffer's size, minus offset, must be at least calcsize(format).  See
help(struct) for more on format strings.
[clinic start generated code]*/

static PyObject *
unpack_from_impl(PyObject *module, PyStructObject *s_object,
                 Py_buffer *buffer, Py_ssize_t offset)
/*[clinic end generated code: output=1042631674c6e0d3 input=599262b23559f6c5]*/
{
    return Struct_unpack_from_impl(s_object, buffer, offset);
}

/*[clinic input]
iter_unpack

    format as s_object: cache_struct
    buffer: object
    /

Return an iterator yielding tuples unpacked from the given bytes.

The bytes are unpacked according to the format string, like a repeated
invocation of unpack_from().  Requires that the bytes length be
a multiple of calcsize(format).
[clinic start generated code]*/

static PyObject *
iter_unpack_impl(PyObject *module, PyStructObject *s_object,
                 PyObject *buffer)
/*[clinic end generated code: output=0ae50e250d20e74d input=ac5086c5c4ed68bb]*/
{
    return Struct_iter_unpack_impl(s_object, buffer);
}

static struct PyMethodDef module_functions[] = {
    _CLEARCACHE_METHODDEF
    CALCSIZE_METHODDEF
    ITER_UNPACK_METHODDEF
    PACK_METHODDEF
    PACK_INTO_METHODDEF
    UNPACK_METHODDEF
    UNPACK_FROM_METHODDEF
    {NULL,       NULL}          /* sentinel */
};


/* Module initialization */

PyDoc_STRVAR(module_doc,
"Functions to convert between Python values and C structs.\n\
Python bytes objects are used to hold the data representing the C struct\n\
and also as format strings (explained below) to describe the layout of data\n\
in the C struct.\n\
\n\
The optional first format char indicates byte order, size and alignment:\n\
  @: native order, size & alignment (default)\n\
  =: native order, std. size & alignment\n\
  <: little-endian, std. size & alignment\n\
  >: big-endian, std. size & alignment\n\
  !: same as >\n\
\n\
The remaining chars indicate types of args and must match exactly;\n\
these can be preceded by a decimal repeat count:\n\
  x: pad byte (no data); c:char; b:signed byte; B:unsigned byte;\n\
  ?:_Bool; h:short; H:unsigned short; i:int; I:unsigned int;\n\
  l:long; L:unsigned long; f:float; d:double; e:half-float.\n\
  F:float complex; D:double complex.\n\
Special cases (preceding decimal count indicates length):\n\
  s:string (array of char); p: pascal string (with count byte).\n\
Special cases (only available in native format):\n\
  n:ssize_t; N:size_t;\n\
  P:an integer type that is wide enough to hold a pointer.\n\
Special case (not in native mode unless 'long long' in platform C):\n\
  q:long long; Q:unsigned long long\n\
Whitespace between formats is ignored.\n\
\n\
The variable struct.error is an exception raised on errors.\n");


static int
_structmodule_traverse(PyObject *module, visitproc visit, void *arg)
{
    _structmodulestate *state = get_struct_state(module);
    if (state) {
        Py_VISIT(state->cache);
        Py_VISIT(state->PyStructType);
        Py_VISIT(state->unpackiter_type);
        Py_VISIT(state->StructError);
    }
    return 0;
}

static int
_structmodule_clear(PyObject *module)
{
    _structmodulestate *state = get_struct_state(module);
    if (state) {
        Py_CLEAR(state->cache);
        Py_CLEAR(state->PyStructType);
        Py_CLEAR(state->unpackiter_type);
        Py_CLEAR(state->StructError);
    }
    return 0;
}

static void
_structmodule_free(void *module)
{
    (void)_structmodule_clear((PyObject *)module);
}

static int
_structmodule_exec(PyObject *m)
{
    _structmodulestate *state = get_struct_state(m);

    state->cache = PyDict_New();
    if (state->cache == NULL) {
        return -1;
    }

    state->PyStructType = PyType_FromModuleAndSpec(
        m, &PyStructType_spec, NULL);
    if (state->PyStructType == NULL) {
        return -1;
    }
    if (PyModule_AddType(m, (PyTypeObject *)state->PyStructType) < 0) {
        return -1;
    }

    state->unpackiter_type = PyType_FromModuleAndSpec(
        m, &unpackiter_type_spec, NULL);
    if (state->unpackiter_type == NULL) {
        return -1;
    }

    /* init cannot fail */
    (void)_PyOnceFlag_CallOnce(&endian_tables_init_once, init_endian_tables, NULL);

    /* Add some symbolic constants to the module */
    state->StructError = PyErr_NewException("struct.error", NULL, NULL);
    if (state->StructError == NULL) {
        return -1;
    }
    if (PyModule_AddObjectRef(m, "error", state->StructError) < 0) {
        return -1;
    }

    return 0;
}

static PyModuleDef_Slot _structmodule_slots[] = {
    _Py_ABI_SLOT,
    {Py_mod_exec, _structmodule_exec},
    {Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED},
    {Py_mod_gil, Py_MOD_GIL_NOT_USED},
    {0, NULL}
};

static struct PyModuleDef _structmodule = {
    PyModuleDef_HEAD_INIT,
    .m_name = "_struct",
    .m_doc = module_doc,
    .m_size = sizeof(_structmodulestate),
    .m_methods = module_functions,
    .m_slots = _structmodule_slots,
    .m_traverse = _structmodule_traverse,
    .m_clear = _structmodule_clear,
    .m_free = _structmodule_free,
};

PyMODINIT_FUNC
PyInit__struct(void)
{
    return PyModuleDef_Init(&_structmodule);
}