obj_long.c File Reference

Big ints, implemented through my own makeshift thing. More...

#include <kuroko/vm.h>
#include <kuroko/value.h>
#include <kuroko/util.h>
#include "private.h"
#include <assert.h>
Include dependency graph for obj_long.c:

Go to the source code of this file.

Data Structures

struct  KrkLong_Internal
struct  BigInt
struct  _private


#define DIGIT_SHIFT   31
#define DIGIT_MAX   0x7FFFFFFF
#define PREP_OUTPUT(res, a, b)   KrkLong _tmp_out_ ## res, *_swap_out_ ## res = NULL; do { if (res == a || res == b) { krk_long_init_si(&_tmp_out_ ## res, 0); _swap_out_ ## res = res; res = &_tmp_out_ ## res; } } while (0)
#define PREP_OUTPUT1(res, a)   KrkLong _tmp_out_ ## res, *_swap_out_ ## res = NULL; do { if (res == a) { krk_long_init_si(&_tmp_out_ ## res, 0); _swap_out_ ## res = res; res = &_tmp_out_ ## res; } } while (0)
#define FINISH_OUTPUT(res)   do { if (_swap_out_ ## res) { _swap(_swap_out_ ## res, res); krk_long_clear(&_tmp_out_ ## res); } } while (0)
#define AS_long(o)   ((struct BigInt *)AS_OBJECT(o))
#define IS_long(o)   (krk_isInstanceOf(o, KRK_BASE_CLASS(long)))
#define CURRENT_CTYPE   struct BigInt *
#define CURRENT_NAME   self
#define NEEDED_BITS   53
#define PRINTER(name, base, prefix)
#define BASIC_BIN_OP(a, b)   BASIC_BIN_OP_FLOATS(a,b,,)
#define FLOAT_A(op)   else if (IS_FLOATING(argv[1])) return FLOATING_VAL(krk_long_get_double(self->value) op AS_FLOATING(argv[1]));
#define FLOAT_B(op)   else if (IS_FLOATING(argv[1])) return FLOATING_VAL(AS_FLOATING(argv[1]) op krk_long_get_double(self->value));
#define BASIC_BIN_OP_FLOAT(a, b, op)   BASIC_BIN_OP_FLOATS(a,b,FLOAT_A(op),FLOAT_B(op))
#define KRK_FLOAT_COMPARE(comp)   else if (IS_FLOATING(argv[1])) return BOOLEAN_VAL(krk_long_get_double(self->value) comp AS_FLOATING(argv[1]));
#define COMPARE_OP(name, comp)
#define DEC_DIGIT_SIZE   sizeof(digit_t)
#define DEC_DIGIT_CNT   9
#define DEC_DIGIT_MAX   1000000000
#define CURRENT_CTYPE   krk_integer_type
#define BIND_METHOD(klass, method)   do { krk_defineNative(& _ ## klass->methods, #method, _ ## klass ## _ ## method); } while (0)
#define BIND_STATICMETHOD(klass, method)   do { krk_defineNativeStaticMethod(& _ ## klass->methods, #method, _ ## klass ## _ ## method); } while (0)
#define BIND_TRIPLET(klass, name)


typedef struct KrkLong_Internal KrkLong
typedef KrkLong krk_long[1]
typedef int(* fmtCallback) (void *, int, int *)
typedef uint32_t digit_t


size_t krk_long_digits_in_base (KrkLong *num, int base)
 Estimate how many digits are needed to convert a long to a base. More...
KrkValue krk_int_from_float (double val)
 KRK_StaticMethod (long, __new__)
KrkValue _long___float__ (int, KrkValue *, int)
KrkValue _long___truediv__ (int, KrkValue *, int)
KrkValue _long___rtruediv__ (int, KrkValue *, int)
KrkValue _long___pow__ (int, KrkValue *, int)
KrkValue _long___rpow__ (int, KrkValue *, int)
_noexport KrkValue krk_long_coerced_pow (krk_integer_type a, krk_integer_type b)
KrkValue _long___hash__ (int, KrkValue *, int)
KrkValue krk_parse_int (const char *start, size_t width, unsigned int base)
KrkValue _long___int__ (int, KrkValue *, int)
KrkValue _long___len__ (int, KrkValue *, int)
KrkValue _long___invert__ (int, KrkValue *, int)
KrkValue _long___neg__ (int, KrkValue *, int)
KrkValue _long___abs__ (int, KrkValue *, int)
KrkValue _long___pos__ (int, KrkValue *, int)
KrkValue krk_doFormatString (const char *typeName, KrkString *format_spec, int positive, void *abs, fmtCallback callback, fmtCallback(*prepCallback)(void *, int))
KrkValue _long___format__ (int, KrkValue *, int)
KrkValue _long_bit_count (int, KrkValue *, int)
KrkValue _long_bit_length (int, KrkValue *, int)
KrkValue _long_to_bytes (int, KrkValue *, int)
KrkValue _long__digit_count (int, KrkValue *, int)
KrkValue _long__get_digit (int, KrkValue *, int)
KrkValue _long___repr__ (int, KrkValue *, int)
KrkValue krk_double_to_string (double a, unsigned int digits, char formatter, int plus, int forcedigits)
 Convert a double to a KrkString. More...
KrkValue krk_parse_float (const char *s, size_t l)
 Parse a string into a float. More...
KrkValue krk_float_to_fraction (double d)
 Convert a double to a tuple of two longs. More...
_protected int krk_long_to_int (KrkValue val, char size, void *out)
 Convert an int or long to a C integer. More...
KrkValue _int_bit_count (int, KrkValue *, int)
KrkValue _int_bit_length (int, KrkValue *, int)
KrkValue _int_to_bytes (int, KrkValue *, int)
_noexport void _createAndBind_longClass (void)

Detailed Description

Big ints, implemented through my own makeshift thing.

K. Lange klang.nosp@m.e@to.nosp@m.aruos.nosp@m..org

Simple, slightly incomplete implementation of a 'long' type. Conceptually, several things were learned from Python: we store our longs as a sequence of 31-bit unsigned digits, combined with a signed count of digits - negative for a negative number, positive for a positive number, and 0 for 0.


  • Expose better functions for extracting and converting native integers, which would be useful in modules that want to take 64-bit values, extracted unsigned values, etc.
  • Faster division for large divisors?
  • Shifts without multiply/divide...

Definition in file obj_long.c.

Macro Definition Documentation


#define BASIC_BIN_OP_FLOATS (   name,
KRK_Method(long,__ ## name ## __) { \
krk_long tmp; \
if (IS_long(argv[1])) krk_long_init_copy(tmp, AS_long(argv[1])->value); \
else if (IS_INTEGER(argv[1])) krk_long_init_si(tmp, AS_INTEGER(argv[1])); \
else return NOTIMPL_VAL(); \
long_func(tmp,self->value,tmp); \
return make_long_obj(tmp); \
} \
KRK_Method(long,__r ## name ## __) { \
krk_long tmp; \
if (IS_long(argv[1])) krk_long_init_copy(tmp, AS_long(argv[1])->value); \
else if (IS_INTEGER(argv[1])) krk_long_init_si(tmp, AS_INTEGER(argv[1])); \
else return NOTIMPL_VAL(); \
long_func(tmp,tmp,self->value); \
return make_long_obj(tmp); \
} \
_noexport \
KrkValue krk_long_coerced_ ## name (krk_integer_type a, krk_integer_type b) { \
krk_long tmp_res, tmp_a, tmp_b; \
krk_long_init_si(tmp_res, 0); \
krk_long_init_si(tmp_a, a); \
krk_long_init_si(tmp_b, b); \
long_func(tmp_res, tmp_a, tmp_b); \
krk_long_clear_many(tmp_a, tmp_b, NULL); \
return make_long_obj(tmp_res); \

Definition at line 1578 of file obj_long.c.


#define BIND_TRIPLET (   klass,
BIND_METHOD(klass,__ ## name ## __); \
BIND_METHOD(klass,__r ## name ## __); \
krk_defineNative(&_ ## klass->methods,"__i" #name "__",_ ## klass ## ___ ## name ## __);

Definition at line 3177 of file obj_long.c.


#define COMPARE_OP (   name,
KRK_Method(long,__ ## name ## __) { \
krk_long tmp; \
if (IS_long(argv[1])) krk_long_init_copy(tmp, AS_long(argv[1])->value); \
else if (IS_INTEGER(argv[1])) krk_long_init_si(tmp, AS_INTEGER(argv[1])); \
else return NOTIMPL_VAL(); \
int cmp = krk_long_compare(self->value,tmp); \
krk_long_clear(tmp); \
return BOOLEAN_VAL(cmp comp 0); \

Definition at line 1799 of file obj_long.c.


#define PRINTER (   name,
KRK_Method(long,__ ## name ## __) { \
size_t size; \
uint32_t hash; \
char * rev = krk_long_to_str(self->value, base, prefix, &size, &hash); \
return OBJECT_VAL(krk_takeStringVetted(rev,size,size,KRK_OBJ_FLAGS_STRING_ASCII,hash)); \
KrkString * krk_takeStringVetted(char *chars, size_t length, size_t codesLength, KrkStringType type, uint32_t hash)
Like krk_takeString but for when the caller has already calculated code lengths, hash,...
Definition: object.c:241

Definition at line 1527 of file obj_long.c.

Typedef Documentation

◆ digit_t

typedef uint32_t digit_t

Huge decimals for fast conversion.

This is a lightweight implementation of decimal-based bigints that only supports addition, inplace subtraction, and multiplication (via Karatsuba). With this, we can much more quickly produce decimal conversions of (binary) longs.

Definition at line 2104 of file obj_long.c.

Function Documentation

◆ _int_bit_count()

KrkValue _int_bit_count ( int  ,
KrkValue ,

int wrapper implementations of the byte conversions.

Convert to a long and just use those versions...

Definition at line 3148 of file obj_long.c.

◆ krk_double_to_string()

KrkValue krk_double_to_string ( double  a,
unsigned int  digits,
char  formatter,
int  plus,
int  forcedigits 

Convert a double to a KrkString.

We approach the problem of string conversion by converting the mantissa of the double to a bigint. We then treat that bigint as part of a fraction with a large power-of-ten denominator, and then apply the 2^n portion represented by the exponent of the double. For n<0, we will increase the magnitude of the fraction by multiplying the top and bottom repeatedly by 10^31, so that the multiplication (actually a right shift) by the 2^n part does not lose any bits. The result of all of this is an exact representation of the numerator of "x" in "x * 10^y = m * 2^n" with a denominator that remains a large power-of-ten. We can then perform decimal string conversion on this, round the decimal result as needed, and piece together the digits to form a whole, fractional, and exponential part.

aDouble value to convert.
digitsDesired precision, meaning varies between e/f and g.
formatterprintf-style formatter character: eEfFgG or ' '
plusWhether to force a sign character when value is positive.
forcedigitsForce trailing zeros, particularly in 'g' formatters.
A KrkValue representing the string.

Definition at line 2562 of file obj_long.c.

◆ krk_float_to_fraction()

KrkValue krk_float_to_fraction ( double  d)

Convert a double to a tuple of two longs.

Turns a floating-point value into a tuple representing a ratio of two integers that is equivalent.

dValue to convert.

Definition at line 2998 of file obj_long.c.

◆ krk_long_digits_in_base()

size_t krk_long_digits_in_base ( KrkLong num,
int  base 

Estimate how many digits are needed to convert a long to a base.

Dumb. Should be exact for a handful of powers of two, overestimates for everything else, so deal with that on your own...

Definition at line 821 of file obj_long.c.

◆ krk_long_to_int()

_protected int krk_long_to_int ( KrkValue  val,
char  size,
void *  out 

Convert an int or long to a C integer.

No overflow checking is performed in any case.

valint or long to convert.
sizeSize in bytes of desired C integer type.
outPointer to resulting int.

Definition at line 3084 of file obj_long.c.

◆ krk_parse_float()

KrkValue krk_parse_float ( const char *  s,
size_t  l 

Parse a string into a float.

The approach we take here is to collect all of the digits left of the exponent (if present), convert them to a big int disregarding the radix point, then multiply or divide that by an appropriate power of ten based on the exponent and location of the radix point. The division step uses are long.__truediv__ to get accurate conversions of fractions to floats.

May raise exceptions if parsing fails, either here or in integer parsing.

sString to parse.
lLength of string to parse.
A Kuroko float value, or None on exceptin.

Definition at line 2820 of file obj_long.c.