8000 py/objint.c: Add support for int.bit_length(). by dmazzella · Pull Request #11679 · micropython/micropython · GitHub
[go: up one dir, main page]
Skip to content

py/objint.c: Add support for int.bit_length(). #11679

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 5 commits into
base: master
Choose a base branch
from
Open

py/objint.c: Add support for int.bit_length(). #11679

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
0811b35
py/objint.c: Add support for int.bit_length
dmazzella Jun 1, 2023
b71f370
code formatting
dmazzella Jun 1, 2023
1747ae9
py/objint.c: Add support for int.bit_length().
dmazzella Jun 1, 2023
9dd4f8f
py/objint.c: Add support for int.bit_length().
dmazzella Jun 1, 2023
d6ee656
py/objint.c: Add support for int.bit_length().
dmazzella Jun 1, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
5 changes: 5 additions & 0 deletions ports/unix/variants/coverage/mpconfigvariant.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -42,3 +42,8 @@
#define MICROPY_TRACKED_ALLOC (1)
#define MICROPY_WARNINGS_CATEGORY (1)
#define MICROPY_PY_UCRYPTOLIB_CTR (1)

// Enable int.bit_length(n)
#ifndef MICROPY_INT_BIT_LENGTH
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This needs to be defined (and defaulted) in mpconfig.h.

In general rather than enabling things in coverage, just make them MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_EVERYTHING in mpconfig, which will be enabled by coverage.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Also for consistency I think this should be called MICROPY_PY_BUILTINS_INT_BIT_LENGTH.

#define MICROPY_INT_BIT_LENGTH (1)
#endif
18 changes: 18 additions & 0 deletions py/mpz.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1390,6 +1390,24 @@ void mpz_pow3_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs, const mpz_t
mpz_free(n);
}

#if MICROPY_INT_BIT_LENGTH
mp_uint_t mpz_bit_length_inpl(mpz_t *n) {
if (n->len == 0) {
return 0;
}

mpz_t *dest = mpz_clone(n);
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Instead of copying the mpz into a new integer and modifying it, you can just count the digits in the mpz.

mp_uint_t num_bits = 0;
while (dest->len > 0) {
dest->len = mpn_shr(dest->dig, dest->dig, dest->len, 1);
num_bits++;
}

mpz_free(dest);
return num_bits;
}
#endif

#if 0
these functions are unused

Expand Down
3 changes: 3 additions & 0 deletions py/mpz.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -138,6 +138,9 @@ void mpz_and_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
void mpz_or_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
void mpz_xor_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs);
void mpz_divmod_inpl(mpz_t *dest_quo, mpz_t *dest_rem, const mpz_t *lhs, const mpz_t *rhs);
#if MICROPY_INT_BIT_LENGTH
mp_uint_t mpz_bit_length_inpl(mpz_t *dest);
#endif

static inline size_t mpz_max_num_bits(const mpz_t *z) {
return z->len * MPZ_DIG_SIZE;
Expand Down
21 changes: 21 additions & 0 deletions py/objint.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -450,9 +450,30 @@ STATIC mp_obj_t int_to_bytes(size_t n_args, const mp_obj_t *args) {
}
STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(int_to_bytes_obj, 3, 4, int_to_bytes);

#if MICROPY_INT_BIT_LENGTH
STATIC mp_obj_t int_bit_length(size_t n_args, const mp_obj_t *args) {
(void)n_args;
#if MICROPY_LONGINT_IMPL == MICROPY_LONGINT_IMPL_MPZ
< E864 span class="Button-content"> Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This unnecessarily creates an mpz if the input is a small int.

Instead, these functions should handle small ints separately, and only send them off to mpz if necessary.

return mp_obj_int_mpz_bit_length(args[0]);
#else
mp_uint_t dest = MP_OBJ_SMALL_INT_VALUE(args[0]);
mp_uint_t num_bits = 0;
while (dest > 0) {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This does not work for negative numbers. It will always return 32 (or 64 depending on sizeof(mp_uint_t)) as it will just keep shifting down the sign bit.

The reason the tests pass with negative numbers is that this code is never hit.

dest >>= 1;
num_bits++;
}
return mp_obj_new_int_from_uint(num_bits);
#endif
}
STATIC MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(int_bit_length_obj, 0, 1, int_bit_length);
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We also need to provide this for the "long long" implementation.

#endif

STATIC const mp_rom_map_elem_t int_locals_dict_table[] = {
{ MP_ROM_QSTR(MP_QSTR_from_bytes), MP_ROM_PTR(&int_from_bytes_obj) },
{ MP_ROM_QSTR(MP_QSTR_to_bytes), MP_ROM_PTR(&int_to_bytes_obj) },
#if MICROPY_INT_BIT_LENGTH
{ MP_ROM_QSTR(MP_QSTR_bit_length), MP_ROM_PTR(&int_bit_length_obj) },
#endif
};

STATIC MP_DEFINE_CONST_DICT(int_locals_dict, int_locals_dict_table);
Expand Down
3 changes: 3 additions & 0 deletions py/objint.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -61,5 +61,8 @@ mp_obj_t mp_obj_int_unary_op(mp_unary_op_t op, mp_obj_t o_in);
mp_obj_t mp_obj_int_binary_op(mp_binary_op_t op, mp_obj_t lhs_in, mp_obj_t rhs_in);
mp_obj_t mp_obj_int_binary_op_extra_cases(mp_binary_op_t op, mp_obj_t lhs_in, mp_obj_t rhs_in);
mp_obj_t mp_obj_int_pow3(mp_obj_t base, mp_obj_t exponent, mp_obj_t modulus);
#if (MICROPY_INT_BIT_LENGTH && MICROPY_LONGINT_IMPL == MICROPY_LONGINT_IMPL_MPZ)
mp_obj_t mp_obj_int_mpz_bit_length(mp_obj_t n);
#endif

#endif // MICROPY_INCLUDED_PY_OBJINT_H
16 changes: 15 additions & 1 deletion py/objint_mpz.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -334,7 +334,7 @@ mp_obj_t mp_obj_int_binary_op(mp_binary_op_t op, mp_obj_t lhs_in, mp_obj_t rhs_i
}
}

#if MICROPY_PY_BUILTINS_POW3
#if (MICROPY_PY_BUILTINS_POW3 || MICROPY_INT_BIT_LENGTH)
STATIC mpz_t *mp_mpz_for_int(mp_obj_t arg, mpz_t *temp) {
if (mp_obj_is_small_int(arg)) {
mpz_init_from_int(temp, MP_OBJ_SMALL_INT_VALUE(arg));
Expand All @@ -344,7 +344,9 @@ STATIC mpz_t *mp_mpz_for_int(mp_obj_t arg, mpz_t *temp) {
return &(arp_p->mpz);
}
}
#endif

#if MICROPY_PY_BUILTINS_POW3
mp_obj_t mp_obj_int_pow3(mp_obj_t base, mp_obj_t exponent, mp_obj_t modulus) {
if (!mp_obj_is_int(base) || !mp_obj_is_int(exponent) || !mp_obj_is_int(modulus)) {
mp_raise_TypeError(MP_ERROR_TEXT("pow() with 3 arguments requires integers"));
Expand Down Expand Up @@ -373,6 +375,18 @@ mp_obj_t mp_obj_int_pow3(mp_obj_t base, mp_obj_t exponent, mp_obj_t modulus) {
}
#endif

#if MICROPY_INT_BIT_LENGTH
mp_obj_t mp_obj_int_mpz_bit_length(mp_obj_t size) {
mpz_t n_temp;
mpz_t *n = mp_mpz_for_int(size, &n_temp);
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As above, if you handle small ints directly, you don't need to allocate an mpz here.

mp_uint_t res = mpz_bit_length_inpl(n);
if (n == &n_temp) {
mpz_deinit(n);
}
return mp_obj_new_int_from_ull(res);
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

res will always fit in a small int, so can just use MP_OBJ_NEW_SMALL_INT directly.

}
#endif

mp_obj_t mp_obj_new_int(mp_int_t value) {
if (MP_SMALL_INT_FITS(value)) {
return MP_OBJ_NEW_SMALL_INT(value);
Expand Down
2 changes: 2 additions & 0 deletions tests/basics/builtin_help.py.exp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,9 +3,11 @@ object <function> is of type function
object <class 'int'> is of type type
from_bytes -- <classmethod>
to_bytes -- <function>
########
object 1 is of type int
from_bytes -- <classmethod>
to_bytes -- <function>
########
object <module 'micropython'> is of type module
__name__ -- micropython
const -- <function>
Expand Down
20 changes: 20 additions & 0 deletions tests/basics/int_bit_length.py
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,20 @@
# tests int.bit_length

try:
int.bit_length
except AttributeError:
print('SKIP')
raise SystemExit

n = -37
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Needs tests for big ints (i.e. mpz). Also some more interesting bit patterns around the boundaries.

print(n.bit_length())

n = 1024
print(n.bit_length())

n = -1024
print(n.bit_length())

print((2048).bit_length())

print((-2048).bit_length())
0