/* Abstract Object Interface (many thanks to Jim Fulton) */

#include "Python.h"

#include <ctype.h>

#include "structmember.h" /* we need the offsetof() macro from there */

#include "longintrepr.h"

#define NEW_STYLE_NUMBER(o) PyType_HasFeature((o)->ob_type, \

				Py_TPFLAGS_CHECKTYPES)

/* Shorthands to return certain errors */

static PyObject *

type_error(const char *msg, PyObject *obj)

{

	PyErr_Format(PyExc_TypeError, msg, obj->ob_type->tp_name);

	return NULL;

}

static PyObject *

null_error(void)

{

	if (!PyErr_Occurred())

		PyErr_SetString(PyExc_SystemError,

				"null argument to internal routine");

	return NULL;

}

/* Operations on any object */

int

PyObject_Cmp(PyObject *o1, PyObject *o2, int *result)

{

	int r;

	if (o1 == NULL || o2 == NULL) {

		null_error();

		return -1;

	}

	r = PyObject_Compare(o1, o2);

	if (PyErr_Occurred())

		return -1;

	*result = r;

	return 0;

}

PyObject *

PyObject_Type(PyObject *o)

{

	PyObject *v;

	if (o == NULL)

		return null_error();

	v = (PyObject *)o->ob_type;

	Py_INCREF(v);

	return v;

}

Py_ssize_t

PyObject_Size(PyObject *o)

{

	PySequenceMethods *m;

	if (o == NULL) {

		null_error();

		return -1;

	}

	m = o->ob_type->tp_as_sequence;

	if (m && m->sq_length)

		return m->sq_length(o);

	return PyMapping_Size(o);

}

#undef PyObject_Length

Py_ssize_t

PyObject_Length(PyObject *o)

{

	return PyObject_Size(o);

}

#define PyObject_Length PyObject_Size

/* The length hint function returns a non-negative value from o.__len__()

   or o.__length_hint__().  If those methods aren't found or return a negative

   value, then the defaultvalue is returned.  This function never fails. 

   Accordingly, it will mask exceptions raised in either method.

*/

Py_ssize_t

_PyObject_LengthHint(PyObject *o, Py_ssize_t defaultvalue)

{

	static PyObject *hintstrobj = NULL;

	PyObject *ro;

	Py_ssize_t rv;

	/* try o.__len__() */

	rv = PyObject_Size(o);

	if (rv >= 0)

		return rv;

	if (PyErr_Occurred())

		PyErr_Clear();

	/* cache a hashed version of the attribute string */

	if (hintstrobj == NULL) {

		hintstrobj = PyString_InternFromString("__length_hint__");

		if (hintstrobj == NULL)

			goto defaultcase;

	}

	/* try o.__length_hint__() */

	ro = PyObject_CallMethodObjArgs(o, hintstrobj, NULL);

	if (ro == NULL)

		goto defaultcase;

	rv = PyInt_AsLong(ro);

	Py_DECREF(ro);

	if (rv >= 0)

		return rv;

defaultcase:

	if (PyErr_Occurred())

		PyErr_Clear();

	return defaultvalue;

}

PyObject *

PyObject_GetItem(PyObject *o, PyObject *key)

{

	PyMappingMethods *m;

	if (o == NULL || key == NULL)

		return null_error();

	m = o->ob_type->tp_as_mapping;

	if (m && m->mp_subscript)

		return m->mp_subscript(o, key);

	if (o->ob_type->tp_as_sequence) {

		if (PyIndex_Check(key)) {

			Py_ssize_t key_value;

			key_value = PyNumber_AsSsize_t(key, PyExc_IndexError);

			if (key_value == -1 && PyErr_Occurred())

				return NULL;

			return PySequence_GetItem(o, key_value);

		}

		else if (o->ob_type->tp_as_sequence->sq_item)

			return type_error("sequence index must "

					  "be integer, not '%.200s'", key);

	}

	return type_error("'%.200s' object is unsubscriptable", o);

}

int

PyObject_SetItem(PyObject *o, PyObject *key, PyObject *value)

{

	PyMappingMethods *m;

	if (o == NULL || key == NULL || value == NULL) {

		null_error();

		return -1;

	}

	m = o->ob_type->tp_as_mapping;

	if (m && m->mp_ass_subscript)

		return m->mp_ass_subscript(o, key, value);

	if (o->ob_type->tp_as_sequence) {

		if (PyIndex_Check(key)) {

			Py_ssize_t key_value;

			key_value = PyNumber_AsSsize_t(key, PyExc_IndexError);

			if (key_value == -1 && PyErr_Occurred())

				return -1;

			return PySequence_SetItem(o, key_value, value);

		}

		else if (o->ob_type->tp_as_sequence->sq_ass_item) {

			type_error("sequence index must be "

				   "integer, not '%.200s'", key);

			return -1;

		}

	}

	type_error("'%.200s' object does not support item assignment", o);

	return -1;

}

int

PyObject_DelItem(PyObject *o, PyObject *key)

{

	PyMappingMethods *m;

	if (o == NULL || key == NULL) {

		null_error();

		return -1;

	}

	m = o->ob_type->tp_as_mapping;

	if (m && m->mp_ass_subscript)

		return m->mp_ass_subscript(o, key, (PyObject*)NULL);

	if (o->ob_type->tp_as_sequence) {

		if (PyIndex_Check(key)) {

			Py_ssize_t key_value;

			key_value = PyNumber_AsSsize_t(key, PyExc_IndexError);

			if (key_value == -1 && PyErr_Occurred())

				return -1;

			return PySequence_DelItem(o, key_value);

		}

		else if (o->ob_type->tp_as_sequence->sq_ass_item) {

			type_error("sequence index must be "

				   "integer, not '%.200s'", key);

			return -1;

		}

	}

	type_error("'%.200s' object does not support item deletion", o);

	return -1;

}

int

PyObject_DelItemString(PyObject *o, char *key)

{

	PyObject *okey;

	int ret;

	if (o == NULL || key == NULL) {

		null_error();

		return -1;

	}

	okey = PyString_FromString(key);

	if (okey == NULL)

		return -1;

	ret = PyObject_DelItem(o, okey);

	Py_DECREF(okey);

	return ret;

}

int

PyObject_AsCharBuffer(PyObject *obj,

			  const char **buffer,

			  Py_ssize_t *buffer_len)

{

	PyBufferProcs *pb;

	char *pp;

	Py_ssize_t len;

	if (obj == NULL || buffer == NULL || buffer_len == NULL) {

		null_error();

		return -1;

	}

	pb = obj->ob_type->tp_as_buffer;

	if (pb == NULL ||

	     pb->bf_getcharbuffer == NULL ||

	     pb->bf_getsegcount == NULL) {

		PyErr_SetString(PyExc_TypeError,

				"expected a character buffer object");

		return -1;

	}

	if ((*pb->bf_getsegcount)(obj,NULL) != 1) {

		PyErr_SetString(PyExc_TypeError,

				"expected a single-segment buffer object");

		return -1;

	}

	len = (*pb->bf_getcharbuffer)(obj, 0, &pp);

	if (len < 0)

		return -1;

	*buffer = pp;

	*buffer_len = len;

	return 0;

}

int

PyObject_CheckReadBuffer(PyObject *obj)

{

	PyBufferProcs *pb = obj->ob_type->tp_as_buffer;

	if (pb == NULL ||

	    pb->bf_getreadbuffer == NULL ||

	    pb->bf_getsegcount == NULL ||

	    (*pb->bf_getsegcount)(obj, NULL) != 1)

		return 0;

	return 1;

}

int PyObject_AsReadBuffer(PyObject *obj,

			  const void **buffer,

			  Py_ssize_t *buffer_len)

{

	PyBufferProcs *pb;

	void *pp;

	Py_ssize_t len;

	if (obj == NULL || buffer == NULL || buffer_len == NULL) {

		null_error();

		return -1;

	}

	pb = obj->ob_type->tp_as_buffer;

	if (pb == NULL ||

	     pb->bf_getreadbuffer == NULL ||

	     pb->bf_getsegcount == NULL) {

		PyErr_SetString(PyExc_TypeError,

				"expected a readable buffer object");

		return -1;

	}

	if ((*pb->bf_getsegcount)(obj, NULL) != 1) {

		PyErr_SetString(PyExc_TypeError,

				"expected a single-segment buffer object");

		return -1;

	}

	len = (*pb->bf_getreadbuffer)(obj, 0, &pp);

	if (len < 0)

		return -1;

	*buffer = pp;

	*buffer_len = len;

	return 0;

}

int PyObject_AsWriteBuffer(PyObject *obj,

			   void **buffer,

			   Py_ssize_t *buffer_len)

{

	PyBufferProcs *pb;

	void*pp;

	Py_ssize_t len;

	if (obj == NULL || buffer == NULL || buffer_len == NULL) {

		null_error();

		return -1;

	}

	pb = obj->ob_type->tp_as_buffer;

	if (pb == NULL ||

	     pb->bf_getwritebuffer == NULL ||

	     pb->bf_getsegcount == NULL) {

		PyErr_SetString(PyExc_TypeError,

				"expected a writeable buffer object");

		return -1;

	}

	if ((*pb->bf_getsegcount)(obj, NULL) != 1) {

		PyErr_SetString(PyExc_TypeError,

				"expected a single-segment buffer object");

		return -1;

	}

	len = (*pb->bf_getwritebuffer)(obj,0,&pp);

	if (len < 0)

		return -1;

	*buffer = pp;

	*buffer_len = len;

	return 0;

}

/* Buffer C-API for Python 3.0 */

int

PyObject_GetBuffer(PyObject *obj, Py_buffer *view, int flags)

{

	if (!PyObject_CheckBuffer(obj)) {

		PyErr_Format(PyExc_TypeError,

                             "'%100s' does not have the buffer interface",

                             Py_TYPE(obj)->tp_name);

		return -1;

	}

	return (*(obj->ob_type->tp_as_buffer->bf_getbuffer))(obj, view, flags);

}

static int

_IsFortranContiguous(Py_buffer *view)

{

	Py_ssize_t sd, dim;

	int i;

	if (view->ndim == 0) return 1;

	if (view->strides == NULL) return (view->ndim == 1);

	sd = view->itemsize;

	if (view->ndim == 1) return (view->shape[0] == 1 ||

				   sd == view->strides[0]);

	for (i=0; i<view->ndim; i++) {

		dim = view->shape[i];

		if (dim == 0) return 1;

		if (view->strides[i] != sd) return 0;

		sd *= dim;

	}

	return 1;

}

static int

_IsCContiguous(Py_buffer *view)

{

	Py_ssize_t sd, dim;

	int i;

	if (view->ndim == 0) return 1;

	if (view->strides == NULL) return 1;

	sd = view->itemsize;

	if (view->ndim == 1) return (view->shape[0] == 1 ||

				   sd == view->strides[0]);

	for (i=view->ndim-1; i>=0; i--) {

		dim = view->shape[i];

		if (dim == 0) return 1;

		if (view->strides[i] != sd) return 0;

		sd *= dim;

	}

	return 1;

}

int

PyBuffer_IsContiguous(Py_buffer *view, char fort)

{

	if (view->suboffsets != NULL) return 0;

	if (fort == 'C')

		return _IsCContiguous(view);

	else if (fort == 'F')

		return _IsFortranContiguous(view);

	else if (fort == 'A')

		return (_IsCContiguous(view) || _IsFortranContiguous(view));

	return 0;

}

void*

PyBuffer_GetPointer(Py_buffer *view, Py_ssize_t *indices)

{

	char* pointer;

	int i;

	pointer = (char *)view->buf;

	for (i = 0; i < view->ndim; i++) {

		pointer += view->strides[i]*indices[i];

		if ((view->suboffsets != NULL) && (view->suboffsets[i] >= 0)) {

			pointer = *((char**)pointer) + view->suboffsets[i];

		}

	}

	return (void*)pointer;

}

static void

_add_one_to_index_F(int nd, Py_ssize_t *index, Py_ssize_t *shape)

{

	int k;

	for (k=0; k<nd; k++) {

		if (index[k] < shape[k]-1) {

			index[k]++;

			break;

		}

		else {

			index[k] = 0;

		}

	}

}

static void

_add_one_to_index_C(int nd, Py_ssize_t *index, Py_ssize_t *shape)

{

	int k;

	for (k=nd-1; k>=0; k--) {

		if (index[k] < shape[k]-1) {

			index[k]++;

			break;

		}

		else {

			index[k] = 0;

		}

	}

}

  /* view is not checked for consistency in either of these.  It is

     assumed that the size of the buffer is view->len in

     view->len / view->itemsize elements.

  */

int

PyBuffer_ToContiguous(void *buf, Py_buffer *view, Py_ssize_t len, char fort)

{

	int k;

	void (*addone)(int, Py_ssize_t *, Py_ssize_t *);

	Py_ssize_t *indices, elements;

	char *dest, *ptr;

	if (len > view->len) {

		len = view->len;

	}

	if (PyBuffer_IsContiguous(view, fort)) {

		/* simplest copy is all that is needed */

		memcpy(buf, view->buf, len);

		return 0;

	}

	/* Otherwise a more elaborate scheme is needed */

	/* XXX(nnorwitz): need to check for overflow! */

	indices = (Py_ssize_t *)PyMem_Malloc(sizeof(Py_ssize_t)*(view->ndim));

	if (indices == NULL) {

		PyErr_NoMemory();

		return -1;

	}

	for (k=0; k<view->ndim;k++) {

		indices[k] = 0;

	}

	if (fort == 'F') {

		addone = _add_one_to_index_F;

	}

	else {

		addone = _add_one_to_index_C;

	}

	dest = buf;

	/* XXX : This is not going to be the fastest code in the world

		 several optimizations are possible.

	 */

	elements = len / view->itemsize;

	while (elements--) {

		addone(view->ndim, indices, view->shape);

		ptr = PyBuffer_GetPointer(view, indices);

		memcpy(dest, ptr, view->itemsize);

		dest += view->itemsize;

	}

	PyMem_Free(indices);

	return 0;

}

int

PyBuffer_FromContiguous(Py_buffer *view, void *buf, Py_ssize_t len, char fort)