This patch regenerates the orders tables and generates both the normal
ones and also those for vertical partitions. I've added a long comment
above the definition of orders[] that explains how they work (there's
no change, but it took me a while to understand, so it's probably a
good thing to document). I've also slightly changed when we use the
orders_vert tables: they are now used for both PARTITION_VERT_A and
PARTITION_VERT_B.

The patch also removes the #if around the partition argument to
has_top_right and adds it to has_bottom_left. (I could have put it
inside an #if, but I shouldn't imagine there's any measurable
performance cost and the code is cleaner this way).

The tables were regenerated with a Haskell script which I've included
at the bottom of the commit message (so the next person doesn't have
to write it from scratch yet again). The output looks reasonably
clean, but clang-format does change it somewhat so you need to run
that afterwards. The tables are also output in a different order, so
you'll need to clean that up by hand too.

-- orders.hs: Print tables to stdout by calling printOrders

import Data.Foldable
import Data.List (findIndex)
import Data.Maybe
import System.Environment
import Text.Printf
import Text.Read

data Block = Block { lbw :: Int, lbh :: Int, vert :: Bool }

minLogBlockSize :: Bool -> Int
minLogBlockSize v = if v then 3 else 2

maxLogBlockSize = 7 :: Int

-- This code generates the inverse of what we want: a mapping from visit order
-- to raster order. That is, element i of the list will be the raster index of
-- the block that we visit at step i.
vrSplit :: Block -> Int -> Int -> Int -> [Int]
vrSplit b stride lsz off
  -- PARTITION_NONE
  | lbw b >= lsz && lbh b >= lsz = [off]
  -- Some form of horizontal partition
  | lbw b < lsz && lbh b >= lsz =
      [off,off + 1..off + 2^(lsz - lbw b) - 1]
  -- Some form of vertical partition
  | lbw b >= lsz && lbh b < lsz =
      [off,off + stride..off + (2^(lsz - lbh b) - 1)*stride]
  -- PARTITION_VERT_*
  | vert b && lbh b + 1 == lsz && lbw b + 1 == lsz =
      [off, off + stride, off + 1, off + stride + 1]
  -- PARTITION_SPLIT
  | otherwise =
    concatMap (vrSplit b stride (lsz - 1))
    [off, off + 2^(lsz - lbw b - 1), off + 2^(lsz - lbh b - 1) * stride,
     off + 2^(lsz - lbw b - 1) + 2^(lsz - lbh b - 1) * stride]

vrOrders :: Block -> [Int]
vrOrders b = vrSplit b (2 ^ (maxLogBlockSize - lbw b)) maxLogBlockSize 0

-- A simple function to invert the bijection generated by vrOrders (it's very
-- naive, but the list isn't exactly long)
invertList :: [Int] -> [Int]
invertList is = map (\ i -> fromJust $ findIndex ((==) i) is) [0..length is - 1]

genOrders :: Block -> [Int]
genOrders = invertList . vrOrders

-- Code to print everything out in the style used in the AOM codebase
forButLast_ :: Applicative f => [a] -> (a -> f b) -> f ()
forButLast_ [] f = pure ()
forButLast_ (a : as) f = fbl a as f
  where fbl a [] f = pure ()
        fbl a (a' : as) f = f a *> fbl a' as f

numDigits :: Int -> Int
numDigits n =
  if n == 0 then 1
  else ceiling $ logBase 10 $ fromIntegral $ 1 + n

printRow :: Int -> Int -> [Int] -> Bool -> IO ()
printRow indent fw as islast = do
  { if null as then return ()
    else do
      { printf "%*s" indent ""
      ; forButLast_ as (\ a -> printf "%d,%*s" a (postDent a) "")
      ; printf "%d%s" (last as) (if islast then "\n" else ",\n") } }
  where postDent a = 1 + fw - numDigits a

printInts :: Int -> Int -> Int -> [Int] -> IO ()
printInts width indent fw [] = return ()
printInts width indent fw as =
  let (row, rest) = splitAt eltsPerLine as in
    printRow indent fw row (null rest) >> printInts width indent fw rest
  where eltsPerLine = quot (width - indent + 1) (fw + 2)

printBlockOrders :: Block -> IO ()
printBlockOrders b = do
  { printf "static const uint16_t orders_%s%dx%d[%d] = {\n"
    (if vert b then "vert_" else "")
    ((2 :: Int) ^ lbw b) ((2 :: Int) ^ lbh b) numElts
  ; printInts 79 2 intWidth (genOrders b)
  ; printf "};\n" }
  where lsz = maxLogBlockSize
        numElts = (2 :: Int) ^ (lsz - lbw b + lsz - lbh b)
        intWidth = max 1 $ ceiling $ logBase 10 $ fromIntegral (numElts - 1)

blocksForWidth :: Bool -> Int -> [Block]
blocksForWidth v lbw = map (\ lbh -> Block lbw lbh v) [minLbh..maxLbh]
  where maxLogAspectRatio = if v then 0 else 2
        minLbh = max (minLogBlockSize v) (lbw - maxLogAspectRatio)
        maxLbh = min maxLogBlockSize (lbw + maxLogAspectRatio)

blocksForV :: Bool -> [Block]
blocksForV v = concatMap (blocksForWidth v) [minLbw..maxLbw]
  where minLbw = (minLogBlockSize v)
        maxLbw = maxLogBlockSize

blocks :: [Block]
blocks = blocksForV False ++ blocksForV True

printOrders :: IO ()
printOrders = traverse_ printBlockOrders blocks

-- Ends orders.hs

BUG=aomedia:914

Change-Id: I6c53e80caa0d203cdc11f88471b6c117c633baa6