typedef long unsigned int size_t;
typedef int HItype __attribute__ ((mode (HI)));

typedef int QItype __attribute__ ((mode (QI)));
typedef unsigned int UQItype __attribute__ ((mode (QI)));
typedef unsigned int UHItype __attribute__ ((mode (HI)));


#define SI_TYPE_SIZE 32
#define __BITS4 (SI_TYPE_SIZE / 4)
#define __ll_B (1L << (SI_TYPE_SIZE / 2))
#define __ll_lowpart(t) ((UQItype) (t) % __ll_B)
#define __ll_highpart(t) ((UQItype) (t) / __ll_B)

#define umul_ppmm(w1, w0, u, v)                                         \
  do {                                                                  \
    UQItype __x0, __x1, __x2, __x3;                                     \
    UQItype __ul, __vl, __uh, __vh;                                     \
                                                                        \
    __ul = __ll_lowpart (u);                                            \
    __uh = __ll_highpart (u);                                           \
    __vl = __ll_lowpart (v);                                            \
    __vh = __ll_highpart (v);                                           \
                                                                        \
    __x0 = (UQItype) __ul * __vl;                                       \
    __x1 = (UQItype) __ul * __vh;                                       \
    __x2 = (UQItype) __uh * __vl;                                       \
    __x3 = (UQItype) __uh * __vh;                                       \
                                                                        \
    __x1 += __ll_highpart (__x0);/* this can't give carry */            \
    __x1 += __x2;               /* but this indeed can */               \
    if (__x1 < __x2)            /* did we get it? */                    \
      __x3 += __ll_B;           /* yes, add it in the proper pos. */    \
                                                                        \
    (w1) = __x3 + __ll_highpart (__x1);                                 \
    (w0) = __ll_lowpart (__x1) * __ll_B + __ll_lowpart (__x0);          \
  } while (0)

#define __umulsidi3(u, v) \
  ({DWunion __w;                                                        \
    umul_ppmm (__w.s.high, __w.s.low, u, v);                            \
    __w.ll; })

struct DWstruct {QItype low, high;};
typedef union
{
  struct DWstruct s;
  HItype ll;
} DWunion;

HItype __aeabi_lmul (HItype u, HItype v) __attribute__((alias ("__muldi3")));
HItype __muldi3 (HItype u, HItype v)
{
  const DWunion uu = {.ll = u};
  const DWunion vv = {.ll = v};
  DWunion w = {.ll = __umulsidi3 (uu.s.low, vv.s.low)};

  w.s.high += ((UQItype) uu.s.low * (UQItype) vv.s.high
        + (UQItype) uu.s.high * (UQItype) vv.s.low);

  return w.ll;
}
