1  /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  2   * gmpy2_mpz_pack.c                                                        *
  3   * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  4   * Python interface to the GMP or MPIR, MPFR, and MPC multiple precision   *
  5   * libraries.                                                              *
  6   *                                                                         *
  7   * Copyright 2000 - 2009 Alex Martelli                                     *
  8   *                                                                         *
  9   * Copyright 2008 - 2021 Case Van Horsen                                   *
 10   *                                                                         *
 11   * This file is part of GMPY2.                                             *
 12   *                                                                         *
 13   * GMPY2 is free software: you can redistribute it and/or modify it under  *
 14   * the terms of the GNU Lesser General Public License as published by the  *
 15   * Free Software Foundation, either version 3 of the License, or (at your  *
 16   * option) any later version.                                              *
 17   *                                                                         *
 18   * GMPY2 is distributed in the hope that it will be useful, but WITHOUT    *
 19   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or   *
 20   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public    *
 21   * License for more details.                                               *
 22   *                                                                         *
 23   * You should have received a copy of the GNU Lesser General Public        *
 24   * License along with GMPY2; if not, see <http://www.gnu.org/licenses/>    *
 25   * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 26  
 27  /*
 28   **************************************************************************
 29   * pack and unpack methods
 30   *
 31   * Both pack and unpack use a devious trick when stuffing values into the
 32   * internal structure of an mpz_t. By setting a bit beyond the range of
 33   * interest, we are guaranteed that memory will remain available. When
 34   * the bit is cleared, it also triggers normalization of the value by
 35   * accounting for leading bits that are zero.
 36   **************************************************************************
 37   */
 38  
 39  PyDoc_STRVAR(doc_pack,
 40  "pack(lst, n) -> mpz\n\n"
 41  "Pack a list of integers 'lst' into a single 'mpz' by concatenating\n"
 42  "each integer element of 'lst' after padding to length n bits. Raises\n"
 43  "an error if any integer is negative or greater than n bits in\n"
 44  "length.");
 45  
 46  static PyObject *
 47  GMPy_MPZ_pack(PyObject *self, PyObject *args)
 48  {
 49      mp_bitcnt_t nbits, total_bits, tempx_bits;
 50      Py_ssize_t index, lst_count, i, temp_bits, limb_count;
 51      PyObject *lst;
 52      mpz_t temp, temp1;
 53      MPZ_Object *result, *tempx = 0;
 54      CTXT_Object *context = NULL;
 55  
 56      if (PyTuple_GET_SIZE(args) != 2) {
 57          TYPE_ERROR("pack() requires 'list','int' arguments");
 58          return NULL;
 59      }
 60  
 61      nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
 62      if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
 63          return NULL;
 64      }
 65  
 66      if (!PyList_Check(PyTuple_GET_ITEM(args, 0))) {
 67          TYPE_ERROR("pack() requires 'list','int' arguments");
 68          return NULL;
 69      }
 70  
 71      if (!(result = GMPy_MPZ_New(context)))
 72          return NULL;
 73  
 74      lst = PyTuple_GET_ITEM(args, 0);
 75      lst_count = PyList_GET_SIZE(lst);
 76      total_bits = nbits * lst_count;
 77  
 78      if ((total_bits / lst_count) != nbits) {
 79          VALUE_ERROR("result too large to store in an 'mpz'");
 80          return NULL;
 81      }
 82  
 83      mpz_set_ui(result->z, 0);
 84      mpz_setbit(result->z, total_bits + (mp_bits_per_limb * 2));
 85  
 86      mpz_init(temp);
 87      mpz_init(temp1);
 88      mpz_set_ui(temp, 0);
 89      limb_count = 0;
 90      tempx_bits = 0;
 91  
 92      for (index = 0; index < lst_count; index++) {
 93          if (!(tempx = GMPy_MPZ_From_Integer(PyList_GetItem(lst, index), context))
 94              || (mpz_sgn(tempx->z) < 0)
 95              || (mpz_sizeinbase(tempx->z,2) > (size_t)nbits)) {
 96              TYPE_ERROR("pack() requires list elements be positive integers < 2^n bits");
 97              mpz_clear(temp);
 98              Py_XDECREF((PyObject*)tempx);
 99              Py_DECREF((PyObject*)result);
100              return NULL;
101          }
102          mpz_mul_2exp(temp1, tempx->z, tempx_bits);
103          mpz_add(temp, temp, temp1);
104          tempx_bits += nbits;
105          i = 0;
106          temp_bits = mpz_sizeinbase(temp, 2) * mpz_sgn(temp);
107          while (tempx_bits >= (mp_bitcnt_t)mp_bits_per_limb) {
108              if (temp_bits > 0) {
109                  result->z->_mp_d[limb_count] = mpz_getlimbn(temp, i);
110              }
111              i += 1;
112              tempx_bits -= mp_bits_per_limb;
113              limb_count += 1;
114              temp_bits -= mp_bits_per_limb;
115          }
116          if (temp_bits > 0) {
117              mpz_tdiv_q_2exp(temp, temp, mp_bits_per_limb * i);
118          }
119          else {
120              mpz_set_ui(temp, 0);
121          }
122          Py_DECREF((PyObject*)tempx);
123      }
124      result->z->_mp_d[limb_count] = mpz_getlimbn(temp, 0);
125      mpz_clrbit(result->z, total_bits + (mp_bits_per_limb * 2));
126      mpz_clear(temp);
127      mpz_clear(temp1);
128      return (PyObject*)result;
129  }
130  
131  PyDoc_STRVAR(doc_unpack,
132  "unpack(x, n) -> list\n\n"
133  "Unpack an integer 'x' into a list of n-bit values. Equivalent to\n"
134  "repeated division by 2**n. Raises error if 'x' is negative.");
135  
136  static PyObject *
137  GMPy_MPZ_unpack(PyObject *self, PyObject *args)
138  {
139      mp_bitcnt_t nbits, total_bits, guard_bit, extra_bits, temp_bits;
140      Py_ssize_t index = 0, lst_count, i, lst_ptr = 0;
141      PyObject *result;
142      mpz_t temp;
143      mp_limb_t extra = 0;
144      MPZ_Object *item, *tempx = NULL;
145      CTXT_Object *context = NULL;
146  
147      if (PyTuple_GET_SIZE(args) != 2) {
148          TYPE_ERROR("unpack() requires 'int','int' arguments");
149          return NULL;
150      }
151  
152      nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
153      if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
154          return NULL;
155      }
156  
157      if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), context))) {
158          TYPE_ERROR("unpack() requires 'int','int' arguments");
159          return NULL;
160      }
161  
162      if (mpz_sgn(tempx->z) < 0) {
163          VALUE_ERROR("unpack() requires x >= 0");
164          return NULL;
165      }
166  
167      if (mpz_sgn(tempx->z) == 0) {
168          total_bits = 0;
169      }
170      else {
171          total_bits = mpz_sizeinbase(tempx->z, 2);
172      }
173  
174      lst_count = total_bits / nbits;
175      if ((total_bits % nbits) || !lst_count) {
176          lst_count += 1;
177      }
178  
179      if (!(result = PyList_New(lst_count))) {
180          Py_DECREF((PyObject*)tempx);
181          return NULL;
182      }
183  
184      if (mpz_sgn(tempx->z) == 0) {
185          if (!(item = GMPy_MPZ_New(context))) {
186              Py_DECREF((PyObject*)tempx);
187              Py_DECREF(result);
188              return NULL;
189          }
190          mpz_set_ui(item->z, 0);
191          PyList_SET_ITEM(result, 0, (PyObject*)item);
192          Py_DECREF((PyObject*)tempx);
193          return result;
194      }
195  
196      mpz_init(temp);
197      guard_bit = nbits + (2 * mp_bits_per_limb);
198      extra_bits = 0;
199      index = 0;
200  
201      while (lst_ptr < lst_count) {
202          i = 0;
203          temp_bits = 0;
204          mpz_set_ui(temp, 0);
205          mpz_setbit(temp, guard_bit);
206          while (temp_bits + extra_bits < nbits) {
207              temp->_mp_d[i++] = mpz_getlimbn(tempx->z, index++);
208              temp_bits += mp_bits_per_limb;
209          }
210          mpz_clrbit(temp, guard_bit);
211          mpz_mul_2exp(temp, temp, extra_bits);
212          if (mpz_sgn(temp) == 0 && extra != 0) {
213              mpz_set_ui(temp, 1);
214              temp->_mp_d[0] = extra;
215          }
216          else {
217             mpn_add_1(temp->_mp_d, temp->_mp_d, mpz_size(temp), extra);
218          }
219          temp_bits += extra_bits;
220  
221          while ((lst_ptr < lst_count) && (temp_bits >= nbits)) {
222              if(!(item = GMPy_MPZ_New(context))) {
223                  mpz_clear(temp);
224                  Py_DECREF((PyObject*)tempx);
225                  Py_DECREF(result);
226                  return NULL;
227              }
228              mpz_tdiv_r_2exp(item->z, temp, nbits);
229              PyList_SET_ITEM(result, lst_ptr++, (PyObject*)item);
230              mpz_tdiv_q_2exp(temp, temp, nbits);
231              temp_bits -= nbits;
232          }
233          extra = mpz_getlimbn(temp, 0);
234          extra_bits = temp_bits;
235      }
236      Py_DECREF((PyObject*)tempx);
237      mpz_clear(temp);
238      return result;
239  }
240  
241