1 /*
2  * Copyright (C) 2021 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.server.display;
18 
19 import java.util.Arrays;
20 import java.util.Comparator;
21 
22 /**
23  * Class which can compute the logical density for a display resolution. It holds a collection
24  * of pre-configured densities, which are used for look-up and interpolation.
25  */
26 public class DensityMapping {
27 
28     // Instead of resolutions we store the squared diagonal size. Diagonals make the map
29     // keys invariant to rotations and are useful for interpolation because they're scalars.
30     // Squared diagonals have the same properties as diagonals (the square function is monotonic)
31     // but also allow us to use integer types and avoid floating point arithmetics.
32     private final Entry[] mSortedDensityMappingEntries;
33 
34     /**
35      * Creates a density mapping. The newly created object takes ownership of the passed array.
36      */
createByOwning(Entry[] densityMappingEntries)37     static DensityMapping createByOwning(Entry[] densityMappingEntries) {
38         return new DensityMapping(densityMappingEntries);
39     }
40 
DensityMapping(Entry[] densityMappingEntries)41     private DensityMapping(Entry[] densityMappingEntries) {
42         Arrays.sort(densityMappingEntries, Comparator.comparingInt(
43                 entry -> entry.squaredDiagonal));
44         mSortedDensityMappingEntries = densityMappingEntries;
45         verifyDensityMapping(mSortedDensityMappingEntries);
46     }
47 
48     /**
49      * Returns the logical density for the given resolution.
50      *
51      * If the resolution matches one of the entries in the mapping, the corresponding density is
52      * returned. Otherwise the return value is interpolated using the closest entries in the map.
53      */
getDensityForResolution(int width, int height)54     public int getDensityForResolution(int width, int height) {
55         int squaredDiagonal = width * width + height * height;
56 
57         // Search for two pre-configured entries "left" and "right" with the following criteria
58         //  * left <= squaredDiagonal
59         //  * squaredDiagonal - left is minimal
60         //  * right > squaredDiagonal
61         //  * right - squaredDiagonal is minimal
62         Entry left = Entry.ZEROES;
63         Entry right = null;
64 
65         for (Entry entry : mSortedDensityMappingEntries) {
66             if (entry.squaredDiagonal <= squaredDiagonal) {
67                 left = entry;
68             } else {
69                 right = entry;
70                 break;
71             }
72         }
73 
74         // Check if we found an exact match.
75         if (left.squaredDiagonal == squaredDiagonal) {
76             return left.density;
77         }
78 
79         // If no configured resolution is higher than the specified resolution, interpolate
80         // between (0,0) and (maxConfiguredDiagonal, maxConfiguredDensity).
81         if (right == null) {
82             right = left;  // largest entry in the sorted array
83             left = Entry.ZEROES;
84         }
85 
86         double leftDiagonal = Math.sqrt(left.squaredDiagonal);
87         double rightDiagonal = Math.sqrt(right.squaredDiagonal);
88         double diagonal = Math.sqrt(squaredDiagonal);
89 
90         return (int) Math.round((diagonal - leftDiagonal) * (right.density - left.density)
91                 / (rightDiagonal - leftDiagonal) + left.density);
92     }
93 
verifyDensityMapping(Entry[] sortedEntries)94     private static void verifyDensityMapping(Entry[] sortedEntries) {
95         for (int i = 1; i < sortedEntries.length; i++) {
96             Entry prev = sortedEntries[i - 1];
97             Entry curr = sortedEntries[i];
98 
99             if (prev.squaredDiagonal == curr.squaredDiagonal) {
100                 // This will most often happen because there are two entries with the same
101                 // resolution (AxB and AxB) or rotated resolution (AxB and BxA), but it can also
102                 // happen in the very rare cases when two different resolutions happen to have
103                 // the same diagonal (e.g. 100x700 and 500x500).
104                 throw new IllegalStateException("Found two entries in the density mapping with"
105                         + " the same diagonal: " + prev + ", " + curr);
106             } else if (prev.density > curr.density) {
107                 throw new IllegalStateException("Found two entries in the density mapping with"
108                         + " increasing diagonal but decreasing density: " + prev + ", " + curr);
109             }
110         }
111     }
112 
113     @Override
toString()114     public String toString() {
115         return "DensityMapping{"
116                 + "mDensityMappingEntries=" + Arrays.toString(mSortedDensityMappingEntries)
117                 + '}';
118     }
119 
120     static class Entry {
121         public static final Entry ZEROES = new Entry(0, 0, 0);
122 
123         public final int squaredDiagonal;
124         public final int density;
125 
Entry(int width, int height, int density)126         Entry(int width, int height, int density) {
127             this.squaredDiagonal = width * width + height * height;
128             this.density = density;
129         }
130 
131         @Override
toString()132         public String toString() {
133             return "DensityMappingEntry{"
134                     + "squaredDiagonal=" + squaredDiagonal
135                     + ", density=" + density + '}';
136         }
137     }
138 }
139