• Rupert Swarbrick's avatar
    Correct has_bottom_left calculation for mixed vertical partitions · 8315daf7
    Rupert Swarbrick authored
    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
    8315daf7
reconintra.c 97.9 KB