Repository: JuliaLang/julia
File: base/int.jl (Julia)

Code before:
signed(::Type{UInt32}) = Int32
signed(::Type{UInt64}) = Int64
signed(::Type{UInt128}) = Int128
signed(::Type{T}) where {T<:Signed} = T

## integer comparisons ##

(<)(x::T, y::T) where {T<:BitSigned}  = slt_int(x, y)

(-)(x::BitInteger)                    = neg_int(x)
(-)(x::T, y::T) where {T<:BitInteger} = sub_int(x, y)
(+)(x::T, y::T) where {T<:BitInteger} = add_int(x, y)
(*)(x::T, y::T) where {T<:BitInteger} = mul_int(x, y)

negate(x) = -x
negate(x::Unsigned) = -convert(Signed, x)
#widenegate(x) = -convert(widen(signed(typeof(x))), x)

inv(x::Integer) = float(one(x)) / float(x)
(/)(x::T, y::T) where {T<:Integer} = float(x) / float(y)
# skip promotion for system integer types
(/)(x::BitInteger, y::BitInteger) = float(x) / float(y)


"""
    mul_hi(a::T, b::T) where {T<:Integer}

Returns the higher half of the product of `a` and `b`.

# Examples
```jldoctest
julia> mul_hi(12345678987654321, 123456789)
82624

julia> (widen(12345678987654321) * 123456789) >> 64
82624

julia> mul_hi(0xff, 0xff)
0xfe
```
"""
function mul_hi(a::T, b::T) where {T<:BitInteger}
    ((widen(a)*b) >>> (sizeof(a)*8)) % T
end

function mul_hi(a::UInt128, b::UInt128)
    shift = sizeof(a)*4
    mask = typemax(UInt128) >> shift
    a1, a2 = a >>> shift, a & mask
    b1, b2 = b >>> shift, b & mask
    a1b1, a1b2, a2b1, a2b2 = a1*b1, a1*b2, a2*b1, a2*b2

Review comment (suggestion):
```suggestion
    mul_hi(a::T, b::T) where {T<:Base.BitInteger}
```
This doesn't yet support general `Integer`s. 

Alternatively, it would be reasonable to declare it with `T <: Integer` if we defined it for other Base integers (i.e. `Bool`, `BigInt`) or decide that we want mul_hi to throw on BigInt, and specify an extensible API that specifies how this should be extended for custom types (e.g. checked and unbounded).

Code after:
signed(::Type{UInt32}) = Int32
signed(::Type{UInt64}) = Int64
signed(::Type{UInt128}) = Int128
signed(::Type{T}) where {T<:Signed} = T

## integer comparisons ##

(<)(x::T, y::T) where {T<:BitSigned}  = slt_int(x, y)

(-)(x::BitInteger)                    = neg_int(x)
(-)(x::T, y::T) where {T<:BitInteger} = sub_int(x, y)
(+)(x::T, y::T) where {T<:BitInteger} = add_int(x, y)
(*)(x::T, y::T) where {T<:BitInteger} = mul_int(x, y)

negate(x) = -x
negate(x::Unsigned) = -convert(Signed, x)
#widenegate(x) = -convert(widen(signed(typeof(x))), x)

inv(x::Integer) = float(one(x)) / float(x)
(/)(x::T, y::T) where {T<:Integer} = float(x) / float(y)
# skip promotion for system integer types
(/)(x::BitInteger, y::BitInteger) = float(x) / float(y)


"""
    mul_hi(a::T, b::T) where {T<:Base.Integer}

Returns the higher half of the product of `a` and `b` where `T` is a fixed size integer.

# Examples
```jldoctest
julia> Base.mul_hi(12345678987654321, 123456789)
82624

julia> (widen(12345678987654321) * 123456789) >> 64
82624

julia> Base.mul_hi(0xff, 0xff)
0xfe
```
"""
function mul_hi(a::T, b::T) where {T<:Integer}
    ((widen(a)*b) >>> Base.top_set_bit(-1 % T)) % T
end

function mul_hi(a::UInt128, b::UInt128)
    shift = sizeof(a)*4
    mask = typemax(UInt128) >> shift
    a1, a2 = a >>> shift, a & mask
    b1, b2 = b >>> shift, b & mask
    a1b1, a1b2, a2b1, a2b2 = a1*b1, a1*b2, a2*b1, a2*b2