/* -*-c-*-
*
- * $Id: mp-arith.c,v 1.10 2001/04/03 19:36:05 mdw Exp $
+ * $Id: mp-arith.c,v 1.11 2002/10/06 22:52:50 mdw Exp $
*
* Basic arithmetic on multiprecision integers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-arith.c,v $
+ * Revision 1.11 2002/10/06 22:52:50 mdw
+ * Pile of changes for supporting two's complement properly.
+ *
* Revision 1.10 2001/04/03 19:36:05 mdw
* Add some simple bitwise operations so that Perl can use them.
*
/*----- Main code ---------------------------------------------------------*/
-/* --- @mp_2c@ --- *
+/* --- @mp_lsl@, @mp_lsr@ --- *
*
- * Arguments: @mp *a@ = source
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
+ * @size_t n@ = number of bits to move
*
- * Returns: Result, @a@ converted to two's complement notation.
+ * Returns: Result, @a@ shifted left or right by @n@.
*/
-mp *mp_2c(mp *d, mp *a)
+mp *mp_lsl(mp *d, mp *a, size_t n)
{
- if (!(a->f & MP_NEG))
- return (MP_COPY(a));
+ MP_DEST(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS, a->f);
+ mpx_lsl(d->v, d->vl, a->v, a->vl, n);
+ d->f = a->f & (MP_NEG | MP_BURN);
+ MP_SHRINK(d);
+ return (d);
+}
+mp *mp_lsr(mp *d, mp *a, size_t n)
+{
MP_DEST(d, MP_LEN(a), a->f);
- mpx_2c(d->v, d->vl, a->v, a->vl);
- d->f = a->f & MP_BURN;
+ mpx_lsr(d->v, d->vl, a->v, a->vl, n);
+ d->f = a->f & (MP_NEG | MP_BURN);
MP_SHRINK(d);
return (d);
}
-/* --- @mp_sm@ --- *
+/* --- @mp_lsl2c@, @mp_lsr2c@ --- *
*
* Arguments: @mp *d@ = destination
* @mp *a@ = source
+ * @size_t n@ = number of bits to move
*
- * Returns: Result, @a@ converted to the native signed-magnitude
- * notation.
+ * Returns: Result, @a@ shifted left or right by @n@. Handles the
+ * pretence of sign-extension for negative numbers.
*/
-mp *mp_sm(mp *d, mp *a)
+mp *mp_lsl2c(mp *d, mp *a, size_t n)
{
- if (!MP_LEN(a) || a->vl[-1] < MPW_MAX / 2)
- return (MP_COPY(a));
+ if (!(a->f & MP_NEG))
+ return (mp_lsl(d, a, n));
+ d = mp_not2c(d, a);
+ d = mp_lsl(d, d, n);
+ d = mp_not2c(d, d);
+ return (d);
+}
- MP_DEST(d, MP_LEN(a), a->f);
- mpx_2c(d->v, d->vl, a->v, a->vl);
- d->f = (a->f & (MP_BURN | MP_NEG)) ^ MP_NEG;
- MP_SHRINK(d);
- return (d);
+mp *mp_lsr2c(mp *d, mp *a, size_t n)
+{
+ if (!(a->f & MP_NEG))
+ return (mp_lsr(d, a, n));
+ d = mp_not2c(d, a);
+ d = mp_lsr(d, d, n);
+ d = mp_not2c(d, d);
+ return (d);
}
-/* --- @mp_lsl@ --- *
+/* --- @mp_testbit@ --- *
*
- * Arguments: @mp *d@ = destination
- * @mp *a@ = source
- * @size_t n@ = number of bits to move
+ * Arguments: @mp *x@ = a large integer
+ * @size_t n@ = which bit to test
*
- * Returns: Result, @a@ shifted left by @n@.
+ * Returns: Nonzero if the bit is set, zero if not.
*/
-mp *mp_lsl(mp *d, mp *a, size_t n)
+int mp_testbit(mp *x, size_t n)
{
- MP_DEST(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS, a->f);
- mpx_lsl(d->v, d->vl, a->v, a->vl, n);
- d->f = a->f & (MP_NEG | MP_BURN);
- MP_SHRINK(d);
- return (d);
+ size_t o;
+ if (n > MPW_BITS * MP_LEN(x))
+ return (0);
+ o = n / MPW_BITS;
+ n %= MPW_BITS;
+ return ((x->v[o] >> n) & 1);
}
-/* --- @mp_lsr@ --- *
+/* --- @mp_testbit2c@ --- *
*
- * Arguments: @mp *d@ = destination
- * @mp *a@ = source
- * @size_t n@ = number of bits to move
+ * Arguments: @mp *x@ = a large integer
+ * @size_t n@ = which bit to test
*
- * Returns: Result, @a@ shifted left by @n@.
+ * Returns: Nonzero if the bit is set, zero if not. Fakes up two's
+ * complement representation.
*/
-mp *mp_lsr(mp *d, mp *a, size_t n)
+int mp_testbit2c(mp *x, size_t n)
{
- MP_DEST(d, MP_LEN(a), a->f);
- mpx_lsr(d->v, d->vl, a->v, a->vl, n);
- d->f = a->f & (MP_NEG | MP_BURN);
- MP_SHRINK(d);
- return (d);
+ int r;
+ if (x->f & MP_NEG)
+ return (mp_testbit(x, n));
+ x = mp_not2c(MP_NEW, x);
+ r = !mp_testbit(x, n);
+ MP_DROP(x);
+ return (r);
}
/* --- @mp_eq@ --- *
return (+1);
}
-/* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- *
+/* --- @mp_bitop@ --- *
*
* Arguments: @mp *d@ = destination
* @mp *a, *b@ = sources
*
- * Returns: The result of the obvious bitwise operation.
+ * Returns: The result of the given bitwise operation. These functions
+ * don't handle negative numbers at all sensibly. For that, use
+ * the @...2c@ variants. The functions are named after the
+ * truth tables they generate:
+ *
+ * a: 0011
+ * b: 0101
+ * @mpx_bitXXXX@
*/
-#define MP_BITBINOP(name) \
+#define MP_BITBINOP(string) \
\
-mp *mp_##name(mp *d, mp *a, mp *b) \
+mp *mp_bit##string(mp *d, mp *a, mp *b) \
{ \
MP_DEST(d, MAX(MP_LEN(a), MP_LEN(b)), a->f | b->f); \
- mpx_##name(d->v, d->vl, a->v, a->vl, b->v, b->vl); \
+ mpx_bit##string(d->v, d->vl, a->v, a->vl, b->v, b->vl); \
d->f = (a->f | b->f) & MP_BURN; \
MP_SHRINK(d); \
return (d); \
}
-MP_BITBINOP(and)
-MP_BITBINOP(or)
-MP_BITBINOP(xor)
+MPX_DOBIN(MP_BITBINOP)
+
+/* --- @mp_not@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
+ *
+ * Returns: The bitwise complement of the source.
+ */
mp *mp_not(mp *d, mp *a)
{
return (d);
}
+/* --- @mp_bitop2c@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *a, *b@ = sources
+ *
+ * Returns: The result of the given bitwise operation. Negative numbers
+ * are treated as two's complement, sign-extended infinitely to
+ * the left. The functions are named after the truth tables
+ * they generate:
+ *
+ * a: 0011
+ * b: 0101
+ * @mpx_bitXXXX@
+ */
+
+/* --- How this actually works --- *
+ *
+ * The two arguments are inverted (with a sign-swap) if they're currently
+ * negative. This means that we end up using a different function (one which
+ * reinverts as we go) for the main operation. Also, if the sign would be
+ * negative at the end, we preinvert the output and then invert again with a
+ * sign-swap.
+ *
+ * Start with: wxyz WXYZ
+ * If @a@ negative: yzwx or YZWX
+ * If @b@ negative: xwzy XWZY
+ * If both negative: zyxw ZYXW
+ */
+
+#define MP_BIT2CBINOP(n, base, an, bn, abn, p_base, p_an, p_bn, p_abn) \
+ \
+mp *mp_bit##n##2c(mp *d, mp *a, mp *b) \
+{ \
+ if (!((a->f | b->f) & MP_NEG)) { /* Both positive */ \
+ d = mp_bit##base(d, a, b); \
+ p_base \
+ } else if (!(b->f & MP_NEG)) { /* Only @b@ positive */ \
+ MP_COPY(b); \
+ d = mp_not2c(d, a); \
+ d = mp_bit##an(d, d, b); \
+ MP_DROP(b); \
+ p_an \
+ } else if (!(a->f & MP_NEG)) { /* Only @a@ positive */ \
+ MP_COPY(a); \
+ d = mp_not2c(d, b); \
+ d = mp_bit##bn(d, a, d); \
+ MP_DROP(a); \
+ p_bn \
+ } else { /* Both negative */ \
+ mp *t = mp_not2c(MP_NEW, a); \
+ mp *d = mp_not2c(d, b); \
+ d = mp_bit##abn(d, t, d); \
+ MP_DROP(t); \
+ p_abn \
+ } \
+ return (d); \
+} \
+
+#define NEG d = mp_not2c(d, d);
+#define POS
+MP_BIT2CBINOP(0000, 0000, 0000, 0000, 0000, POS, POS, POS, POS)
+MP_BIT2CBINOP(0001, 0001, 0100, 0010, 0111, POS, POS, POS, NEG)
+MP_BIT2CBINOP(0010, 0010, 0111, 0001, 0100, POS, NEG, POS, POS)
+MP_BIT2CBINOP(0011, 0011, 0011, 0011, 0011, POS, NEG, POS, NEG)
+MP_BIT2CBINOP(0100, 0100, 0001, 0111, 0010, POS, POS, NEG, POS)
+MP_BIT2CBINOP(0101, 0101, 0101, 0101, 0101, POS, POS, NEG, NEG)
+MP_BIT2CBINOP(0110, 0110, 0110, 0110, 0110, POS, NEG, NEG, POS)
+MP_BIT2CBINOP(0111, 0111, 0010, 0100, 0001, POS, NEG, NEG, NEG)
+MP_BIT2CBINOP(1000, 0111, 0010, 0100, 0001, NEG, POS, POS, POS)
+MP_BIT2CBINOP(1001, 0110, 0110, 0110, 0110, NEG, POS, POS, NEG)
+MP_BIT2CBINOP(1010, 0101, 0101, 0101, 0101, NEG, NEG, POS, POS)
+MP_BIT2CBINOP(1011, 0100, 0001, 0111, 0010, NEG, NEG, POS, NEG)
+MP_BIT2CBINOP(1100, 0011, 0011, 0011, 0011, NEG, POS, NEG, POS)
+MP_BIT2CBINOP(1101, 0010, 0111, 0001, 0100, NEG, POS, NEG, NEG)
+MP_BIT2CBINOP(1110, 0001, 0100, 0010, 0111, NEG, NEG, NEG, POS)
+MP_BIT2CBINOP(1111, 0000, 0000, 0000, 0000, NEG, NEG, NEG, NEG)
+#undef NEG
+#undef POS
+
+/* --- @mp_not2c@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
+ *
+ * Returns: The sign-extended complement of the argument.
+ */
+
+mp *mp_not2c(mp *d, mp *a)
+{
+ mpw one = 1;
+
+ MP_DEST(d, MP_LEN(a) + 1, a->f);
+ if (d == a) {
+ if (a->f & MP_NEG)
+ MPX_USUBN(d->v, d->vl, 1);
+ else
+ MPX_UADDN(d->v, d->vl, 1);
+ } else {
+ if (a->f & MP_NEG)
+ mpx_usub(d->v, d->vl, a->v, a->vl, &one, &one + 1);
+ else
+ mpx_uadd(d->v, d->vl, a->v, a->vl, &one, &one + 1);
+ }
+ d->f = (a->f & (MP_NEG | MP_BURN)) ^ MP_NEG;
+ MP_SHRINK(d);
+ return (d);
+}
+
/* --- @mp_add@ --- *
*
* Arguments: @mp *d@ = destination
RIG(lsl, mp_lsl)
RIG(lsr, mp_lsr)
+RIG(lsl2c, mp_lsl2c)
+RIG(lsr2c, mp_lsr2c)
#undef RIG
return (ok);
}
+static int tbin(dstr *v)
+{
+ static mp *(*fn[])(mp *, mp *, mp *) = {
+#define DO(string) mp_bit##string##2c,
+MPX_DOBIN(DO)
+#undef DO
+ };
+ int ok = 1;
+ unsigned op = 0;
+ mp *a = *(mp **)v[1].buf;
+ mp *b = *(mp **)v[2].buf;
+ mp *r = *(mp **)v[3].buf;
+ mp *c;
+
+ if (strcmp(v[0].buf, "and") == 0) op = 1;
+ else if (strcmp(v[0].buf, "or") == 0) op = 7;
+ else if (strcmp(v[0].buf, "nand") == 0) op = 14;
+ else if (strcmp(v[0].buf, "nor") == 0) op = 8;
+ else if (strcmp(v[0].buf, "xor") == 0) op = 6;
+ else {
+ char *p = v[0].buf;
+ while (*p) {
+ op <<= 1;
+ if (*p++ == '1')
+ op |= 1;
+ }
+ }
+
+ c = fn[op](MP_NEW, a, b);
+ ok = verify(v[0].buf, r, c, a, b);
+ mp_drop(a); mp_drop(b); mp_drop(r); mp_drop(c);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
static int todd(dstr *v)
{
mp *a = *(mp **)v[0].buf;
}
static test_chunk tests[] = {
- { "lsl", tlsl, { &type_mp, &type_mp, &type_mp, 0 } },
- { "lsr", tlsr, { &type_mp, &type_mp, &type_mp, 0 } },
+ { "lsl", tlsl, { &type_mp, &type_int, &type_mp, 0 } },
+ { "lsr", tlsr, { &type_mp, &type_int, &type_mp, 0 } },
+ { "lsl2c", tlsl2c, { &type_mp, &type_int, &type_mp, 0 } },
+ { "lsr2c", tlsr2c, { &type_mp, &type_int, &type_mp, 0 } },
{ "add", tadd, { &type_mp, &type_mp, &type_mp, 0 } },
{ "sub", tsub, { &type_mp, &type_mp, &type_mp, 0 } },
{ "mul", tmul, { &type_mp, &type_mp, &type_mp, 0 } },
{ "div", tdiv, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
+ { "bin2c", tbin, { &type_string, &type_mp, &type_mp, &type_mp, 0 } },
{ "odd", todd, { &type_mp, &type_uint32, &type_mp, 0 } },
{ 0, 0, { 0 } },
};
/* -*-c-*-
*
- * $Id: mp-io.c,v 1.4 2000/06/17 11:45:09 mdw Exp $
+ * $Id: mp-io.c,v 1.5 2002/10/06 22:52:50 mdw Exp $
*
* Loading and storing of multiprecision integers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-io.c,v $
+ * Revision 1.5 2002/10/06 22:52:50 mdw
+ * Pile of changes for supporting two's complement properly.
+ *
* Revision 1.4 2000/06/17 11:45:09 mdw
* Major memory management overhaul. Added arena support. Use the secure
* arena for secret integers. Replace and improve the MP management macros
return (sz);
}
+/* --- @mp_octets2c@ --- *
+ *
+ * Arguments: @const mp *m@ = a multiprecision integer
+ *
+ * Returns: The number of octets required to represent @m@.
+ *
+ * Use: Calculates the external storage required for a multiprecision
+ * integer represented as two's complement.
+ */
+
+size_t mp_octets2c(const mp *m)
+{
+ size_t sz;
+ MPX_OCTETS2C(sz, m->v, m->vl);
+ return (sz);
+}
+
/* --- @mp_bits@ --- *
*
* Arguments: @const mp *m@ = a multiprecision integer
mpx_storeb(m->v, m->vl, pv, sz);
}
+/* --- @mp_loadl2c@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @const void *pv@ = pointer to source data
+ * @size_t sz@ = size of the source data
+ *
+ * Returns: Resulting multiprecision number.
+ *
+ * Use: Loads a multiprecision number from an array of octets as
+ * two's complement. The first byte in the array is the least
+ * significant.
+ */
+
+mp *mp_loadl2c(mp *d, const void *pv, size_t sz)
+{
+ const octet *ov = pv;
+ MP_DEST(d, MPW_RQ(sz), MP_UNDEF);
+ if (!sz || !(ov[sz - 1] & 0x80)) {
+ mpx_loadl(d->v, d->vl, pv, sz);
+ d->f &= ~MP_NEG;
+ } else {
+ mpx_loadl2cn(d->v, d->vl, pv, sz);
+ d->f |= MP_NEG;
+ }
+ d->f &= ~MP_UNDEF;
+ mp_shrink(d);
+ return (d);
+}
+
+/* --- @mp_storel2c@ --- *
+ *
+ * Arguments: @const mp *m@ = source
+ * @void *pv@ = pointer to output array
+ * @size_t sz@ = size of the output array
+ *
+ * Returns: ---
+ *
+ * Use: Stores a multiprecision number in an array of octets as two's
+ * complement. The first byte in the array is the least
+ * significant. If the array is too small to represent the
+ * number, high-order bits are truncated; if the array is too
+ * large, high order bytes are sign-extended.
+ */
+
+void mp_storel2c(const mp *m, void *pv, size_t sz)
+{
+ if (m->f & MP_NEG)
+ mpx_storel2cn(m->v, m->vl, pv, sz);
+ else
+ mpx_storel(m->v, m->vl, pv, sz);
+}
+
+/* --- @mp_loadb2c@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @const void *pv@ = pointer to source data
+ * @size_t sz@ = size of the source data
+ *
+ * Returns: Resulting multiprecision number.
+ *
+ * Use: Loads a multiprecision number from an array of octets as
+ * two's complement. The last byte in the array is the least
+ * significant.
+ */
+
+mp *mp_loadb2c(mp *d, const void *pv, size_t sz)
+{
+ const octet *ov = pv;
+ MP_DEST(d, MPW_RQ(sz), MP_UNDEF);
+ if (!sz || !(ov[0] & 0x80)) {
+ mpx_loadl(d->v, d->vl, pv, sz);
+ d->f &= ~MP_NEG;
+ } else {
+ mpx_loadl2cn(d->v, d->vl, pv, sz);
+ d->f |= MP_NEG;
+ }
+ d->f &= ~MP_UNDEF;
+ mp_shrink(d);
+ return (d);
+}
+
+/* --- @mp_storeb2c@ --- *
+ *
+ * Arguments: @const mp *m@ = source
+ * @void *pv@ = pointer to output array
+ * @size_t sz@ = size of the output array
+ *
+ * Returns: ---
+ *
+ * Use: Stores a multiprecision number in an array of octets, as
+ * two's complement. The last byte in the array is the least
+ * significant. If the array is too small to represent the
+ * number, high-order bits are truncated; if the array is too
+ * large, high order bytes are sign-extended.
+ */
+
+void mp_storeb2c(const mp *m, void *pv, size_t sz)
+{
+ if (m->f & MP_NEG)
+ mpx_storeb2cn(m->v, m->vl, pv, sz);
+ else
+ mpx_storeb(m->v, m->vl, pv, sz);
+}
+
/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: mp.h,v 1.12 2001/06/16 12:57:43 mdw Exp $
+ * $Id: mp.h,v 1.13 2002/10/06 22:52:50 mdw Exp $
*
* Simple multiprecision arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp.h,v $
+ * Revision 1.13 2002/10/06 22:52:50 mdw
+ * Pile of changes for supporting two's complement properly.
+ *
* Revision 1.12 2001/06/16 12:57:43 mdw
* Move the @mpmont_factor@ structure and rename it now that it's used for
* Barrett simultaneous exponentiation too.
extern size_t mp_octets(const mp */*m*/);
+/* --- @mp_octets2c@ --- *
+ *
+ * Arguments: @const mp *m@ = a multiprecision integer
+ *
+ * Returns: The number of octets required to represent @m@.
+ *
+ * Use: Calculates the external storage required for a multiprecision
+ * integer represented as two's complement.
+ */
+
+extern size_t mp_octets2c(const mp */*m*/);
+
/* --- @mp_bits@ --- *
*
* Arguments: @const mp *m@ = a multiprecision integer
extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/);
-/*----- Simple arithmetic -------------------------------------------------*/
-
-/* --- @mp_2c@ --- *
+/* --- @mp_loadl2c@ --- *
*
* Arguments: @mp *d@ = destination
- * @mp *a@ = source
+ * @const void *pv@ = pointer to source data
+ * @size_t sz@ = size of the source data
+ *
+ * Returns: Resulting multiprecision number.
*
- * Returns: Result, @a@ converted to two's complement notation.
+ * Use: Loads a multiprecision number from an array of octets as
+ * two's complement. The first byte in the array is the least
+ * significant.
*/
-extern mp *mp_2c(mp */*d*/, mp */*a*/);
+extern mp *mp_loadl2c(mp */*d*/, const void */*pv*/, size_t /*sz*/);
-/* --- @mp_sm@ --- *
+/* --- @mp_storel2c@ --- *
+ *
+ * Arguments: @const mp *m@ = source
+ * @void *pv@ = pointer to output array
+ * @size_t sz@ = size of the output array
+ *
+ * Returns: ---
+ *
+ * Use: Stores a multiprecision number in an array of octets as two's
+ * complement. The first byte in the array is the least
+ * significant. If the array is too small to represent the
+ * number, high-order bits are truncated; if the array is too
+ * large, high order bytes are sign-extended.
+ */
+
+extern void mp_storel2c(const mp */*m*/, void */*pv*/, size_t /*sz*/);
+
+/* --- @mp_loadb2c@ --- *
*
* Arguments: @mp *d@ = destination
- * @mp *a@ = source
+ * @const void *pv@ = pointer to source data
+ * @size_t sz@ = size of the source data
*
- * Returns: Result, @a@ converted to the native signed-magnitude
- * notation.
+ * Returns: Resulting multiprecision number.
+ *
+ * Use: Loads a multiprecision number from an array of octets as
+ * two's complement. The last byte in the array is the least
+ * significant.
*/
-extern mp *mp_sm(mp */*d*/, mp */*a*/);
+extern mp *mp_loadb2c(mp */*d*/, const void */*pv*/, size_t /*sz*/);
+
+/* --- @mp_storeb2c@ --- *
+ *
+ * Arguments: @const mp *m@ = source
+ * @void *pv@ = pointer to output array
+ * @size_t sz@ = size of the output array
+ *
+ * Returns: ---
+ *
+ * Use: Stores a multiprecision number in an array of octets, as
+ * two's complement. The last byte in the array is the least
+ * significant. If the array is too small to represent the
+ * number, high-order bits are truncated; if the array is too
+ * large, high order bytes are sign-extended.
+ */
+
+extern void mp_storeb2c(const mp */*m*/, void */*pv*/, size_t /*sz*/);
+
+/*----- Simple arithmetic -------------------------------------------------*/
-/* --- @mp_lsl@ --- *
+/* --- @mp_lsl@, @mp_lsr@ --- *
*
* Arguments: @mp *d@ = destination
* @mp *a@ = source
* @size_t n@ = number of bits to move
*
- * Returns: Result, @a@ shifted left by @n@.
+ * Returns: Result, @a@ shifted left or right by @n@.
*/
extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/);
+extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/);
-/* --- @mp_lsr@ --- *
+/* --- @mp_lsl2c@, @mp_lsr2c@ --- *
*
* Arguments: @mp *d@ = destination
* @mp *a@ = source
* @size_t n@ = number of bits to move
*
- * Returns: Result, @a@ shifted left by @n@.
+ * Returns: Result, @a@ shifted left or right by @n@. Handles the
+ * pretence of sign-extension for negative numbers.
*/
-extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/);
+extern mp *mp_lsl2c(mp */*d*/, mp */*a*/, size_t /*n*/);
+extern mp *mp_lsr2c(mp */*d*/, mp */*a*/, size_t /*n*/);
+
+/* --- @mp_testbit@ --- *
+ *
+ * Arguments: @mp *x@ = a large integer
+ * @size_t n@ = which bit to test
+ *
+ * Returns: Nonzero if the bit is set, zero if not.
+ */
+
+extern int mp_testbit(mp */*x*/, size_t /*n*/);
+
+/* --- @mp_testbit2c@ --- *
+ *
+ * Arguments: @mp *x@ = a large integer
+ * @size_t n@ = which bit to test
+ *
+ * Returns: Nonzero if the bit is set, zero if not. Fakes up two's
+ * complement representation.
+ */
+
+extern int mp_testbit2c(mp */*x*/, size_t /*n*/);
/* --- @mp_eq@ --- *
*
#define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
-/* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- *
+/* --- @mp_bitop@ --- *
*
* Arguments: @mp *d@ = destination
* @mp *a, *b@ = sources
*
- * Returns: The result of the obvious bitwise operation.
+ * Returns: The result of the given bitwise operation. These functions
+ * don't handle negative numbers at all sensibly. For that, use
+ * the @...2c@ variants. The functions are named after the
+ * truth tables they generate:
+ *
+ * a: 0011
+ * b: 0101
+ * @mpx_bitXXXX@
*/
-extern mp *mp_and(mp */*d*/, mp */*a*/, mp */*b*/);
-extern mp *mp_or(mp */*d*/, mp */*a*/, mp */*b*/);
-extern mp *mp_xor(mp */*d*/, mp */*a*/, mp */*b*/);
+#define MP_BITDECL(string) \
+ extern mp *mp_bit##string(mp */*d*/, mp */*a*/, mp */*b*/);
+MPX_DOBIN(MP_BITDECL)
+
+/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- *
+ *
+ * Synonyms for the commonly-used functions.
+ */
+
+#define mp_and mp_bit0001
+#define mp_or mp_bit0111
+#define mp_nand mp_bit1110
+#define mp_nor mp_bit1000
+#define mp_xor mp_bit0110
+
+/* --- @mp_not@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
+ *
+ * Returns: The bitwise complement of the source.
+ */
+
extern mp *mp_not(mp */*d*/, mp */*a*/);
+/* --- @mp_bitop2c@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *a, *b@ = sources
+ *
+ * Returns: The result of the given bitwise operation. Negative numbers
+ * are treated as two's complement, sign-extended infinitely to
+ * the left. The functions are named after the truth tables
+ * they generate:
+ *
+ * a: 0011
+ * b: 0101
+ * @mpx_bitXXXX@
+ */
+
+#define MP_BIT2CDECL(string) \
+ extern mp *mp_bit##string##2c(mp */*d*/, mp */*a*/, mp */*b*/);
+MPX_DOBIN(MP_BIT2CDECL)
+
+/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- *
+ *
+ * Synonyms for the commonly-used functions.
+ */
+
+#define mp_and2c mp_bit00012c
+#define mp_or2c mp_bit01112c
+#define mp_nand2c mp_bit11102c
+#define mp_nor2c mp_bit10002c
+#define mp_xor2c mp_bit01102c
+
+/* --- @mp_not2c@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
+ *
+ * Returns: The sign-extended complement of the argument.
+ */
+
+extern mp *mp_not2c(mp */*d*/, mp */*a*/);
+
/* --- @mp_add@ --- *
*
* Arguments: @mp *d@ = destination
/* -*-c-*-
*
- * $Id: mpx.c,v 1.11 2001/04/03 19:36:05 mdw Exp $
+ * $Id: mpx.c,v 1.12 2002/10/06 22:52:50 mdw Exp $
*
* Low-level multiprecision arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx.c,v $
+ * Revision 1.12 2002/10/06 22:52:50 mdw
+ * Pile of changes for supporting two's complement properly.
+ *
* Revision 1.11 2001/04/03 19:36:05 mdw
* Add some simple bitwise operations so that Perl can use them.
*
MPX_ZERO(v, vl);
}
+/* --- @mpx_storel2cn@ --- *
+ *
+ * Arguments: @const mpw *v, *vl@ = base and limit of source vector
+ * @void *pp@ = pointer to octet array
+ * @size_t sz@ = size of octet array
+ *
+ * Returns: ---
+ *
+ * Use: Stores a negative MP in an octet array, least significant
+ * octet first, as two's complement. High-end octets are
+ * silently discarded if there isn't enough space for them.
+ * This obviously makes the output bad.
+ */
+
+void mpx_storel2cn(const mpw *v, const mpw *vl, void *pp, size_t sz)
+{
+ unsigned c = 1;
+ unsigned b = 0;
+ mpw n, w = 0;
+ octet *p = pp, *q = p + sz;
+ unsigned bits = 0;
+
+ while (p < q) {
+ if (bits < 8) {
+ if (v >= vl) {
+ b = w;
+ break;
+ }
+ n = *v++;
+ b = w | n << bits;
+ w = n >> (8 - bits);
+ bits += MPW_BITS - 8;
+ } else {
+ b = w;
+ w >>= 8;
+ bits -= 8;
+ }
+ b = U8(~b + c);
+ c = !b;
+ *p++ = b;
+ }
+ while (p < q) {
+ b = U8(~b + c);
+ c = !b;
+ *p++ = b;
+ b = 0;
+ }
+}
+
+/* --- @mpx_loadl2cn@ --- *
+ *
+ * Arguments: @mpw *v, *vl@ = base and limit of destination vector
+ * @const void *pp@ = pointer to octet array
+ * @size_t sz@ = size of octet array
+ *
+ * Returns: ---
+ *
+ * Use: Loads a negative MP in an octet array, least significant
+ * octet first, as two's complement. High-end octets are
+ * ignored if there isn't enough space for them. This probably
+ * means you made the wrong choice coming here.
+ */
+
+void mpx_loadl2cn(mpw *v, mpw *vl, const void *pp, size_t sz)
+{
+ unsigned n;
+ unsigned c = 1;
+ mpw w = 0;
+ const octet *p = pp, *q = p + sz;
+ unsigned bits = 0;
+
+ if (v >= vl)
+ return;
+ while (p < q) {
+ n = U8(~(*p++) + c);
+ c = !n;
+ w |= n << bits;
+ bits += 8;
+ if (bits >= MPW_BITS) {
+ *v++ = MPW(w);
+ w = n >> (MPW_BITS - bits + 8);
+ bits -= MPW_BITS;
+ if (v >= vl)
+ return;
+ }
+ }
+ *v++ = w;
+ MPX_ZERO(v, vl);
+}
+
+/* --- @mpx_storeb2cn@ --- *
+ *
+ * Arguments: @const mpw *v, *vl@ = base and limit of source vector
+ * @void *pp@ = pointer to octet array
+ * @size_t sz@ = size of octet array
+ *
+ * Returns: ---
+ *
+ * Use: Stores a negative MP in an octet array, most significant
+ * octet first, as two's complement. High-end octets are
+ * silently discarded if there isn't enough space for them,
+ * which probably isn't what you meant.
+ */
+
+void mpx_storeb2cn(const mpw *v, const mpw *vl, void *pp, size_t sz)
+{
+ mpw n, w = 0;
+ unsigned b = 0;
+ unsigned c = 1;
+ octet *p = pp, *q = p + sz;
+ unsigned bits = 0;
+
+ while (q > p) {
+ if (bits < 8) {
+ if (v >= vl) {
+ b = w;
+ break;
+ }
+ n = *v++;
+ b = w | n << bits;
+ w = n >> (8 - bits);
+ bits += MPW_BITS - 8;
+ } else {
+ b = w;
+ w >>= 8;
+ bits -= 8;
+ }
+ b = U8(~b + c);
+ c = !b;
+ *--q = b;
+ }
+ while (q > p) {
+ b = ~b + c;
+ c = !(b & 0xff);
+ *--q = b;
+ b = 0;
+ }
+}
+
+/* --- @mpx_loadb2cn@ --- *
+ *
+ * Arguments: @mpw *v, *vl@ = base and limit of destination vector
+ * @const void *pp@ = pointer to octet array
+ * @size_t sz@ = size of octet array
+ *
+ * Returns: ---
+ *
+ * Use: Loads a negative MP in an octet array, most significant octet
+ * first as two's complement. High-end octets are ignored if
+ * there isn't enough space for them. This probably means you
+ * chose this function wrongly.
+ */
+
+void mpx_loadb2cn(mpw *v, mpw *vl, const void *pp, size_t sz)
+{
+ unsigned n;
+ unsigned c = 1;
+ mpw w = 0;
+ const octet *p = pp, *q = p + sz;
+ unsigned bits = 0;
+
+ if (v >= vl)
+ return;
+ while (q > p) {
+ n = U8(~(*--q) + c);
+ c = !n;
+ w |= n << bits;
+ bits += 8;
+ if (bits >= MPW_BITS) {
+ *v++ = MPW(w);
+ w = n >> (MPW_BITS - bits + 8);
+ bits -= MPW_BITS;
+ if (v >= vl)
+ return;
+ }
+ }
+ *v++ = w;
+ MPX_ZERO(v, vl);
+}
+
/*----- Logical shifting --------------------------------------------------*/
/* --- @mpx_lsl@ --- *
/*----- Bitwise operations ------------------------------------------------*/
-/* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- *
+/* --- @mpx_bitop@ --- *
*
* Arguments: @mpw *dv, *dvl@ = destination vector
* @const mpw *av, *avl@ = first source vector
*
* Returns: ---
*
- * Use; Does the obvious bitwise operations.
+ * Use; Provides the dyadic boolean functions.
*/
-#define MPX_BITBINOP(name, op) \
+#define MPX_BITBINOP(string) \
\
-void mpx_##name(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, \
- const mpw *bv, const mpw *bvl) \
+void mpx_bit##string(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, \
+ const mpw *bv, const mpw *bvl) \
{ \
MPX_SHRINK(av, avl); \
MPX_SHRINK(bv, bvl); \
mpw a, b; \
a = (av < avl) ? *av++ : 0; \
b = (bv < bvl) ? *bv++ : 0; \
- *dv++ = a op b; \
+ *dv++ = MPX_B##string(a, b); \
} \
}
-MPX_BITBINOP(and, &)
-MPX_BITBINOP(or, |)
-MPX_BITBINOP(xor, ^)
+MPX_DOBIN(MPX_BITBINOP)
void mpx_not(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl)
{
return (ok);
}
+static int twocl(dstr *v)
+{
+ dstr d = DSTR_INIT;
+ mpw *m, *ml;
+ size_t sz;
+ int ok = 1;
+
+ sz = v[0].len; if (v[1].len > sz) sz = v[1].len;
+ dstr_ensure(&d, sz);
+
+ sz = MPW_RQ(sz);
+ m = xmalloc(MPWS(sz));
+ ml = m + sz;
+
+ mpx_loadl(m, ml, v[0].buf, v[0].len);
+ mpx_storel2cn(m, ml, d.buf, v[1].len);
+ if (memcmp(d.buf, v[1].buf, v[1].len)) {
+ dumpbits("\n*** storel2cn failed", d.buf, v[1].len);
+ ok = 0;
+ }
+
+ mpx_loadl2cn(m, ml, v[1].buf, v[1].len);
+ mpx_storel(m, ml, d.buf, v[0].len);
+ if (memcmp(d.buf, v[0].buf, v[0].len)) {
+ dumpbits("\n*** loadl2cn failed", d.buf, v[0].len);
+ ok = 0;
+ }
+
+ if (!ok) {
+ dumpbits("pos", v[0].buf, v[0].len);
+ dumpbits("neg", v[1].buf, v[1].len);
+ }
+
+ free(m);
+ dstr_destroy(&d);
+
+ return (ok);
+}
+
+static int twocb(dstr *v)
+{
+ dstr d = DSTR_INIT;
+ mpw *m, *ml;
+ size_t sz;
+ int ok = 1;
+
+ sz = v[0].len; if (v[1].len > sz) sz = v[1].len;
+ dstr_ensure(&d, sz);
+
+ sz = MPW_RQ(sz);
+ m = xmalloc(MPWS(sz));
+ ml = m + sz;
+
+ mpx_loadb(m, ml, v[0].buf, v[0].len);
+ mpx_storeb2cn(m, ml, d.buf, v[1].len);
+ if (memcmp(d.buf, v[1].buf, v[1].len)) {
+ dumpbits("\n*** storeb2cn failed", d.buf, v[1].len);
+ ok = 0;
+ }
+
+ mpx_loadb2cn(m, ml, v[1].buf, v[1].len);
+ mpx_storeb(m, ml, d.buf, v[0].len);
+ if (memcmp(d.buf, v[0].buf, v[0].len)) {
+ dumpbits("\n*** loadb2cn failed", d.buf, v[0].len);
+ ok = 0;
+ }
+
+ if (!ok) {
+ dumpbits("pos", v[0].buf, v[0].len);
+ dumpbits("neg", v[1].buf, v[1].len);
+ }
+
+ free(m);
+ dstr_destroy(&d);
+
+ return (ok);
+}
+
static int lsl(dstr *v)
{
mpw *a, *al;
static test_chunk defs[] = {
{ "load-store", loadstore, { &type_hex, 0 } },
+ { "2cl", twocl, { &type_hex, &type_hex, } },
+ { "2cb", twocb, { &type_hex, &type_hex, } },
{ "lsl", lsl, { &type_hex, &type_int, &type_hex, 0 } },
{ "lsr", lsr, { &type_hex, &type_int, &type_hex, 0 } },
{ "uadd", uadd, { &type_hex, &type_hex, &type_hex, 0 } },
/* -*-c-*-
*
- * $Id: mpx.h,v 1.12 2001/04/03 19:36:05 mdw Exp $
+ * $Id: mpx.h,v 1.13 2002/10/06 22:52:50 mdw Exp $
*
* Low level multiprecision arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx.h,v $
+ * Revision 1.13 2002/10/06 22:52:50 mdw
+ * Pile of changes for supporting two's complement properly.
+ *
* Revision 1.12 2001/04/03 19:36:05 mdw
* Add some simple bitwise operations so that Perl can use them.
*
*/
#define MPX_OCTETS(o, v, vl) do { \
- const mpw *_v = (v), *_vl = (vl); \
- MPX_SHRINK(_v, _vl); \
- if (_v == _vl) \
- (o) = 0; \
- else { \
- size_t _o = (MPW_BITS / 8) * (_vl - _v - 1); \
- mpw _w = _vl[-1]; \
- unsigned _k = MPW_BITS / 2; \
- while (_k >= 8) { \
- if (_w >> _k) { \
- _w >>= _k; \
- _o += _k >> 3; \
- } \
- _k >>= 1; \
- } \
- if (_w) \
- _o++; \
- (o) = _o; \
- } \
+ unsigned long _bb; \
+ MPX_BITS(_bb, (v), (vl)); \
+ (o) = (_bb + 7) >> 3; \
+} while (0)
+
+/* --- @MPX_OCTETS2C@ --- *
+ *
+ * Arguments: @size_t o@ = result variable
+ * @const mpw *v, *vl@ = pointer to array of words
+ *
+ * Use: Calculates the number of octets in a multiprecision value, if
+ * you represent it as two's complement.
+ */
+
+#define MPX_OCTETS2C(o, v, vl) do { \
+ unsigned long _bb; \
+ MPX_BITS(_bb, (v), (vl)); \
+ (o) = (_bb >> 3) + 1; \
} while (0)
/* --- @MPX_COPY@ --- *
extern void mpx_loadb(mpw */*v*/, mpw */*vl*/,
const void */*p*/, size_t /*sz*/);
+/* --- @mpx_storel2cn@ --- *
+ *
+ * Arguments: @const mpw *v, *vl@ = base and limit of source vector
+ * @void *pp@ = pointer to octet array
+ * @size_t sz@ = size of octet array
+ *
+ * Returns: ---
+ *
+ * Use: Stores a negative MP in an octet array, least significant
+ * octet first, as two's complement. High-end octets are
+ * silently discarded if there isn't enough space for them.
+ * This obviously makes the output bad.
+ */
+
+extern void mpx_storel2cn(const mpw */*v*/, const mpw */*vl*/,
+ void */*p*/, size_t /*sz*/);
+
+/* --- @mpx_loadl2cn@ --- *
+ *
+ * Arguments: @mpw *v, *vl@ = base and limit of destination vector
+ * @const void *pp@ = pointer to octet array
+ * @size_t sz@ = size of octet array
+ *
+ * Returns: ---
+ *
+ * Use: Loads a negative MP in an octet array, least significant
+ * octet first, as two's complement. High-end octets are
+ * ignored if there isn't enough space for them. This probably
+ * means you made the wrong choice coming here.
+ */
+
+extern void mpx_loadl2cn(mpw */*v*/, mpw */*vl*/,
+ const void */*p*/, size_t /*sz*/);
+
+/* --- @mpx_storeb2cn@ --- *
+ *
+ * Arguments: @const mpw *v, *vl@ = base and limit of source vector
+ * @void *pp@ = pointer to octet array
+ * @size_t sz@ = size of octet array
+ *
+ * Returns: ---
+ *
+ * Use: Stores a negative MP in an octet array, most significant
+ * octet first, as two's complement. High-end octets are
+ * silently discarded if there isn't enough space for them,
+ * which probably isn't what you meant.
+ */
+
+extern void mpx_storeb2cn(const mpw */*v*/, const mpw */*vl*/,
+ void */*p*/, size_t /*sz*/);
+
+/* --- @mpx_loadb2cn@ --- *
+ *
+ * Arguments: @mpw *v, *vl@ = base and limit of destination vector
+ * @const void *pp@ = pointer to octet array
+ * @size_t sz@ = size of octet array
+ *
+ * Returns: ---
+ *
+ * Use: Loads a negative MP in an octet array, most significant octet
+ * first as two's complement. High-end octets are ignored if
+ * there isn't enough space for them. This probably means you
+ * chose this function wrongly.
+ */
+
+extern void mpx_loadb2cn(mpw */*v*/, mpw */*vl*/,
+ const void */*p*/, size_t /*sz*/);
+
+
/*----- Logical shifting --------------------------------------------------*/
/* --- @mpx_lsl@ --- *
/*----- Bitwise operations ------------------------------------------------*/
-/* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- *
+/* --- How to implement them --- *
+ *
+ * x: 0011
+ * y: 0101
+ */
+
+#define MPX_B0000(x, y) (0u)
+#define MPX_B0001(x, y) ((x) & (y))
+#define MPX_B0010(x, y) ((x) & ~(y))
+#define MPX_B0011(x, y) (x)
+#define MPX_B0100(x, y) (~(x) & ~(y))
+#define MPX_B0101(x, y) (y)
+#define MPX_B0110(x, y) ((x) ^ (y))
+#define MPX_B0111(x, y) ((x) | (y))
+#define MPX_B1000(x, y) (~((x) | (y)))
+#define MPX_B1001(x, y) (~((x) ^ (y)))
+#define MPX_B1010(x, y) (~(y))
+#define MPX_B1011(x, y) ((x) | ~(y))
+#define MPX_B1100(x, y) (~(x))
+#define MPX_B1101(x, y) (~(x) | (y))
+#define MPX_B1110(x, y) (~((x) & (y)))
+#define MPX_B1111(x, y) (~0u)
+
+/* --- @mpx_bitop@ --- *
*
* Arguments: @mpw *dv, *dvl@ = destination vector
* @const mpw *av, *avl@ = first source vector
*
* Returns: ---
*
- * Use; Does the obvious bitwise operations.
+ * Use: Provide the dyadic boolean functions. The functions are
+ * named after the truth table they generate:
+ *
+ * a: 0011
+ * b: 0101
+ * @mpx_bitXXXX@
*/
-extern void mpx_and(mpw */*dv*/, mpw */*dvl*/,
- const mpw */*av*/, const mpw */*avl*/,
- const mpw */*bv*/, const mpw */*bvl*/);
+#define MPX_DOBIN(what) \
+ what(0000) what(0001) what(0010) what(0011) \
+ what(0100) what(0101) what(0110) what(0111) \
+ what(1000) what(1001) what(1010) what(1011) \
+ what(1100) what(1101) what(1110) what(1111)
-extern void mpx_or(mpw */*dv*/, mpw */*dvl*/,
- const mpw */*av*/, const mpw */*avl*/,
- const mpw */*bv*/, const mpw */*bvl*/);
+#define MPX_BITDECL(string) \
+ extern void mpx_bit##string(mpw */*dv*/, mpw */*dvl*/, \
+ const mpw */*av*/, const mpw */*avl*/, \
+ const mpw */*bv*/, const mpw */*bvl*/);
+MPX_DOBIN(MPX_BITDECL)
-extern void mpx_xor(mpw */*dv*/, mpw */*dvl*/,
- const mpw */*av*/, const mpw */*avl*/,
- const mpw */*bv*/, const mpw */*bvl*/);
+/* --- @mpx_[n]and@, @mpx_[n]or@, @mpx_xor@ --- *
+ *
+ * Synonyms for the commonly-used functions above.
+ */
+
+#define mpx_and mpx_bit0001
+#define mpx_or mpx_bit0111
+#define mpx_nand mpx_bit1110
+#define mpx_nor mpx_bit1000
+#define mpx_xor mpx_bit0110
+
+/* --- @mpx_not@ --- *
+ *
+ * Arguments: @mpw *dv, *dvl@ = destination vector
+ * @const mpw *av, *avl@ = first source vector
+ *
+ * Returns: ---
+ *
+ * Use; Bitwise NOT.
+ */
extern void mpx_not(mpw */*dv*/, mpw */*dvl*/,
const mpw */*av*/, const mpw */*avl*/);
# Test vectors for MP functions
#
-# $Id: mp,v 1.9 2001/05/07 17:32:23 mdw Exp $
+# $Id: mp,v 1.10 2002/10/06 22:52:50 mdw Exp $
add {
5 4 9; 5 -4 1; -5 4 -1; -5 -4 -9;
9 4 2 1; -9 4 -3 3; 9 -4 -3 -3; -9 -4 2 -1;
}
+bin2c {
+ and 5 3 1;
+ or 5 3 7;
+ xor 5 3 6;
+ 1111 0 0 -1;
+ xor 0x343cd5 -0x6a49c -0x32984f;
+}
+
+lsr2c {
+ -1 5 -1;
+ 1 5 0;
+ -6 2 -2;
+}
+
odd {
1 0 1;
2 1 1;
# Test vectors for low-level MP functions
#
-# $Id: mpx,v 1.7 2000/07/15 10:03:13 mdw Exp $
+# $Id: mpx,v 1.8 2002/10/06 22:52:50 mdw Exp $
# --- Load-store tests ---
#
522f8b1de257972a25ec49c9ff56340e2684e847ef2fa4d5714d7c8d454e90f6;
}
+# --- Two's complement tests ---
+
+2cb {
+ "" "";
+ 00 00;
+ 000000 00000000000000000000;
+ 01 ff;
+ 0123456789abcdef fedcba9876543211;
+ 0123456789abcdef fffffffedcba9876543211;
+ 0100000000 ffffff00000000;
+}
+
+2cl {
+ "" "";
+ 00 00;
+ 000000 00000000000000000000;
+ 01 ff;
+ efcdab8967452301 1132547698badcfe;
+ efcdab8967452301 1132547698badcfeffffffff;
+ 0000000001 00000000ffffffff;
+}
+
# --- Shift tests ---
lsl {
projects / u / mdw / catacomb / commitdiff