1// Copyright 2014 PDFium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6// Original code is licensed as follows:
7/*
8 * Copyright 2009 ZXing authors
9 *
10 * Licensed under the Apache License, Version 2.0 (the "License");
11 * you may not use this file except in compliance with the License.
12 * You may obtain a copy of the License at
13 *
14 *      http://www.apache.org/licenses/LICENSE-2.0
15 *
16 * Unless required by applicable law or agreed to in writing, software
17 * distributed under the License is distributed on an "AS IS" BASIS,
18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19 * See the License for the specific language governing permissions and
20 * limitations under the License.
21 */
22
23#include "barcode.h"
24#include "BC_UtilRSS.h"
25CBC_UtilRSS::CBC_UtilRSS() {}
26CBC_UtilRSS::~CBC_UtilRSS() {}
27CFX_Int32Array* CBC_UtilRSS::GetRssWidths(int32_t val,
28                                          int32_t n,
29                                          int32_t elements,
30                                          int32_t maxWidth,
31                                          FX_BOOL noNarrow) {
32  CFX_Int32Array* iTemp = new CFX_Int32Array;
33  iTemp->SetSize(elements);
34  CBC_AutoPtr<CFX_Int32Array> widths(iTemp);
35  int32_t bar;
36  int32_t narrowMask = 0;
37  for (bar = 0; bar < elements - 1; bar++) {
38    narrowMask |= (1 << bar);
39    int32_t elmWidth = 1;
40    int32_t subVal;
41    while (TRUE) {
42      subVal = Combins(n - elmWidth - 1, elements - bar - 2);
43      if (noNarrow && (narrowMask == 0) &&
44          (n - elmWidth - (elements - bar - 1) >= elements - bar - 1)) {
45        subVal -= Combins(n - elmWidth - (elements - bar), elements - bar - 2);
46      }
47      if (elements - bar - 1 > 1) {
48        int32_t lessVal = 0;
49        for (int32_t mxwElement = n - elmWidth - (elements - bar - 2);
50             mxwElement > maxWidth; mxwElement--) {
51          lessVal += Combins(n - elmWidth - mxwElement - 1, elements - bar - 3);
52        }
53        subVal -= lessVal * (elements - 1 - bar);
54      } else if (n - elmWidth > maxWidth) {
55        subVal--;
56      }
57      val -= subVal;
58      if (val < 0) {
59        break;
60      }
61      elmWidth++;
62      narrowMask &= ~(1 << bar);
63    }
64    val += subVal;
65    n -= elmWidth;
66    (*widths)[bar] = elmWidth;
67  }
68  (*widths)[bar] = n;
69  return widths.release();
70}
71int32_t CBC_UtilRSS::GetRSSvalue(CFX_Int32Array& widths,
72                                 int32_t maxWidth,
73                                 FX_BOOL noNarrow) {
74  int32_t elements = widths.GetSize();
75  int32_t n = 0;
76  for (int32_t i = 0; i < elements; i++) {
77    n += widths[i];
78  }
79  int32_t val = 0;
80  int32_t narrowMask = 0;
81  for (int32_t bar = 0; bar < elements - 1; bar++) {
82    int32_t elmWidth;
83    for (elmWidth = 1, narrowMask |= (1 << bar); elmWidth < widths[bar];
84         elmWidth++, narrowMask &= ~(1 << bar)) {
85      int32_t subVal = Combins(n - elmWidth - 1, elements - bar - 2);
86      if (noNarrow && (narrowMask == 0) &&
87          (n - elmWidth - (elements - bar - 1) >= elements - bar - 1)) {
88        subVal -= Combins(n - elmWidth - (elements - bar), elements - bar - 2);
89      }
90      if (elements - bar - 1 > 1) {
91        int32_t lessVal = 0;
92        for (int32_t mxwElement = n - elmWidth - (elements - bar - 2);
93             mxwElement > maxWidth; mxwElement--) {
94          lessVal += Combins(n - elmWidth - mxwElement - 1, elements - bar - 3);
95        }
96        subVal -= lessVal * (elements - 1 - bar);
97      } else if (n - elmWidth > maxWidth) {
98        subVal--;
99      }
100      val += subVal;
101    }
102    n -= elmWidth;
103  }
104  return val;
105}
106int32_t CBC_UtilRSS::Combins(int32_t n, int32_t r) {
107  int32_t maxDenom;
108  int32_t minDenom;
109  if (n - r > r) {
110    minDenom = r;
111    maxDenom = n - r;
112  } else {
113    minDenom = n - r;
114    maxDenom = r;
115  }
116  int32_t val = 1;
117  int32_t j = 1;
118  for (int32_t i = n; i > maxDenom; i--) {
119    val *= i;
120    if (j <= minDenom) {
121      val /= j;
122      j++;
123    }
124  }
125  while (j <= minDenom) {
126    val /= j;
127    j++;
128  }
129  return val;
130}
131CFX_Int32Array* CBC_UtilRSS::Elements(CFX_Int32Array& eDist,
132                                      int32_t N,
133                                      int32_t K) {
134  CFX_Int32Array* widths = new CFX_Int32Array;
135  widths->SetSize(eDist.GetSize() + 2);
136  int32_t twoK = K << 1;
137  (*widths)[0] = 1;
138  int32_t i;
139  int32_t minEven = 10;
140  int32_t barSum = 1;
141  for (i = 1; i < twoK - 2; i += 2) {
142    (*widths)[i] = eDist[i - 1] - (*widths)[i - 1];
143    (*widths)[i + 1] = eDist[i] - (*widths)[i];
144    barSum += (*widths)[i] + (*widths)[i + 1];
145    if ((*widths)[i] < minEven) {
146      minEven = (*widths)[i];
147    }
148  }
149  (*widths)[twoK - 1] = N - barSum;
150  if ((*widths)[twoK - 1] < minEven) {
151    minEven = (*widths)[twoK - 1];
152  }
153  if (minEven > 1) {
154    for (i = 0; i < twoK; i += 2) {
155      (*widths)[i] += minEven - 1;
156      (*widths)[i + 1] -= minEven - 1;
157    }
158  }
159  return widths;
160}
161