Hexadecimal midpoint spacer

sequencer.ex

defmodule Sequencer do
  @base 256

  def find_mid(a, b, n \\ 1) do
    [a, b] = ensure_order([a, b])

    ad = bin_to_list(a)
    bd = bin_to_list(b)

    intermediate_bytes = long_linspace(ad, bd, n)

    intermediate_bytes
    |> Enum.map(fn %{den: den, rem: rem, res: bytes} ->
      Enum.concat(bytes, rem_to_byte(rem, den))
    end)
    |> List.insert_at(0, ad)
    |> List.insert_at(-1, bd)
    |> chop_successive_bytes()
    |> List.delete_at(0)
    |> List.delete_at(-1)
    |> Enum.map(fn byte_list -> Enum.into(byte_list, <<>>, fn byte -> <<byte>> end) end)
  end

  ## PRIVATE FUNCTIONS

  def chop_successive_bytes(byte_lists) do
    [h | byte_lists] = byte_lists

    Enum.reduce(byte_lists, [h], fn list, acc ->
      [prev | _] = Enum.reverse(acc)

      slice_at =
        list
        |> Enum.with_index()
        |> Enum.find_index(fn {byte, i} -> Enum.at(prev, i) != byte end)

      Enum.concat(acc, [Enum.slice(list, 0, slice_at + 1)])
    end)
  end

  def rem_to_byte(rem, den) do
    places = Float.ceil(:math.log(den) / :math.log(@base))
    scale = :math.pow(@base, places)

    round(rem / den * scale)
    |> Integer.digits(@base)
    |> leftpad(places)
  end

  defp long_add_same_len(a, b, rem, den) when length(a) == length(b) do
    carry = rem >= den
    rem = if carry, do: rem - den, else: rem
    acc = %{carry: carry, res: b}

    a
    |> Enum.with_index()
    |> List.foldr(acc, fn {ai, i}, %{carry: carry, res: res} ->
      result = ai + Enum.at(b, i) + if carry, do: 1, else: 0
      carry = result >= @base
      res = List.replace_at(res, i, if(carry, do: result - @base, else: result))
      %{carry: carry, res: res}
    end)
    |> Map.put(:rem, rem)
    |> Map.put(:den, den)
  end

  defp long_div(bytes, den) do
    Enum.reduce(bytes, %{res: [], rem: 0, den: den}, fn byte, acc ->
      num = byte + acc.rem * @base

      %{
        res: Enum.concat(acc.res, [floor(num / den)]),
        rem: rem(num, den),
        den: den
      }
    end)
  end

  defp long_linspace(a, b, n) do
    len_a = length(a)
    len_b = length(b)

    a = if len_a < len_b, do: rightpad(a, len_b), else: a
    b = if len_b < len_a, do: rightpad(b, len_a), else: b

    a_div = long_div(a, n + 1)
    b_div = long_div(b, n + 1)

    {as, bs} =
      if n >= 2 do
        Enum.reduce(2..n, {[a_div], [b_div]}, fn i, {as, bs} ->
          a = Enum.at(as, i - 2)
          b = Enum.at(bs, i - 2)

          {
            Enum.concat(as, [long_add_same_len(a.res, a_div.res, a_div.rem + a.rem, n + 1)]),
            Enum.concat(bs, [long_add_same_len(b.res, b_div.res, b_div.rem + b.rem, n + 1)])
          }
        end)
      else
        {[a_div], [b_div]}
      end

    as
    |> Enum.reverse()
    |> Enum.zip(bs)
    |> Enum.map(fn {a, b} ->
      long_add_same_len(a.res, b.res, a.rem + b.rem, n + 1)
      |> Map.drop([:carry])
    end)
  end

  defp ensure_order([a, b]) do
    if a > b, do: [b, a], else: [a, b]
  end

  defp bin_to_list(bytes) when is_list(bytes), do: bytes
  defp bin_to_list(string) when is_binary(string), do: :binary.bin_to_list(string)

  defp rightpad(arr, length) do
    padlen = max(0, length - length(arr))

    if padlen == 0 do
      arr
    else
      0..(padlen - 1) |> Enum.reduce(arr, fn _, acc -> Enum.concat(acc, [0]) end)
    end
  end

  defp leftpad(arr, length) do
    padlen = max(0, length - length(arr))

    if padlen == 0 do
      arr
    else
      0..(padlen - 1) |> Enum.reduce(arr, fn _, acc -> Enum.concat([0], acc) end)
    end
  end
end