#include <stdlib.h>
#include "hackers.h"

struct ms magic(int d)
{ // Must have 2 <= d <= 2**31-1
    // or -2**31 <= d <= -2.
    int p;
    unsigned ad, anc, delta, q1, r1, q2, r2, t;
    const unsigned two31 = 0x80000000; // 2**31.
    struct ms mag;

    ad = abs(d);
    t = two31 + ((unsigned)d >> 31);
    anc = t - 1 - t % ad; // Absolute value of nc.

    p = 31;                // Init. p.
    q1 = two31 / anc;      // Init. q1 = 2**p/|nc|.
    r1 = two31 - q1 * anc; // Init. r1 = rem(2**p, |nc|).
    q2 = two31 / ad;       // Init. q2 = 2**p/|d|.
    r2 = two31 - q2 * ad;  // Init. r2 = rem(2**p, |d|).

    do
    {
        p = p + 1;
        q1 = 2 * q1; // Update q1 = 2**p/|nc|.
        r1 = 2 * r1; // Update r1 = rem(2**p, |nc|).
        if (r1 >= anc)
        {                // (Must be an unsigned
            q1 = q1 + 1; // comparison here.)
            r1 = r1 - anc;
        }
        q2 = 2 * q2; // Update q2 = 2**p/|d|.
        r2 = 2 * r2; // Update r2 = rem(2**p, |d|).
        if (r2 >= ad)
        {                // (Must be an unsigned
            q2 = q2 + 1; // comparison here.)
            r2 = r2 - ad;
        }
        delta = ad - r2;
    } while (q1 < delta || (q1 == delta && r1 == 0));

    mag.M = q2 + 1;
    if (d < 0)
        mag.M = -mag.M; // Magic number and

    mag.s = p - 32; // shift amount to return.
    return mag;
}