Introduction

Improving the run-time performance of R code is critical for handling large datasets and complex computations, especially in machine learning, applied AI, data mining, and statistical analysis. This lesson explores several approaches, ranging from optimizing data structures to parallel computing techniques, with the objective to make R code more efficient.

Many of the techniques presented in this lesson are universally applicable, particularly to other interpreted languages like Python and JavaScript. The relative slowness of R and Python compared to languages like Java and C++ can be attributed to several factors related to their design philosophies, runtime environments, and typical use cases. Understanding these differences is essential when choosing an approach to code optimization.

Firstly, R and Python are interpreted languages, whereas Java and C++ are compiled languages. In interpreted languages, code is executed line by line by an interpreter at runtime, which introduces overhead because the interpreter needs to parse and execute each line of code dynamically. In contrast, compiled languages like Java and C++ are translated into machine code before execution, allowing the CPU to run the code directly without the overhead of interpretation. This compilation step generally results in faster execution times for Java and C++ programs.

R and Python are also dynamically typed languages. This means that type checking happens at runtime rather than at compile time. While this provides greater flexibility and ease of use, it incurs additional overhead because the interpreter must manage type information and perform type checking during execution. Java and C++, being statically typed languages, perform type checking at compile time, which helps optimize the generated machine code for better performance.

Another significant factor for the poorer run-time performance of R and Python are in the way both manage memory. R and Python use automatic garbage collection to manage memory, which periodically frees up memory that is no longer in use. While this simplifies memory management for the programmer, it can cause unpredictable pauses in program execution as the garbage collector runs. Java also uses garbage collection but benefits from more advanced and optimized garbage collection algorithms compared to those typically found in R and Python. C++, on the other hand, requires manual memory management by the programmer, which affords full control over memory allocation and deallocation. This programmer-driven approach allows for highly optimized memory usage but requires careful programming to avoid memory leaks and other issues.

The standard libraries and data structures provided by R and Python are designed for ease of use and flexibility rather than raw performance. For example, Python’s list and dictionary objects are highly flexible but not as efficient as Java’s or C++’s array and hash table implementations. Similarly, R’s data frame and list structures prioritize convenience and ease of manipulation over performance. In contrast, Java and C++ standard libraries are often designed with performance in mind, providing more efficient data structures and algorithms. In fact, many of the high-performance functions in third-party packages for R and Python are written in C++ or Java.

R and Python are also heavily used in data analysis, scientific computing, and machine learning, where the ease of prototyping and the availability of extensive libraries (such as NumPy, pandas, and scikit-learn in Python, and caret, psych, data.table and ggplot2 in R) are more critical than raw execution speed. These languages often serve as “glue” languages, where performance-critical parts of the code are implemented in more efficient languages like C or C++ and then called from R or Python. This approach leverages the strengths of both high-level and low-level languages. It is not unusual for exploration and research to be done in R and Python and then, once an approach is settled upon, the code is rewritten for performance in Java or C++. In fact, R Notebooks allow code chunks to be in R, Python, Java, SQL, and C++ which provides full control to the programmer.

Furthermore, R and Python emphasize readability and ease of use, which can sometimes lead to less efficient code. For example, Python’s use of dynamic typing and high-level data structures encourages a programming style that may be more intuitive but less efficient. Java and C++, in contrast, encourage more explicit and optimized programming practices due to their statically typed nature and lower-level control over system resources.

Lastly, the execution model of these languages differs. R, for example, is designed for statistical computing and data analysis, where typical workloads involve vectorized operations and data manipulation tasks that can be more efficiently handled by specialized libraries written in C or even (good old) FORTRAN. Python, while more general-purpose, is often used in similar domains and benefits from extensive C and C++ extensions to mitigate performance issues.

In short, the slowness of R and Python compared to Java and C++ stems from their interpreted nature, dynamic typing, memory management strategies, and design priorities that emphasize ease of use and flexibility over raw performance. Understanding these trade-offs is essential for selecting the right language for your specific application and for leveraging the strengths of each language effectively.

A final word and caution: An experienced programmer always begins by writing correct code that is simple and easy to follow. Run-time is secondary to correctness. Only if the performance of the code does not meet essential non-functional requirements, should changes to the code be entertained. Improvement must proceed in stages, starting with the simplest modifications.

Measuring Performance

Any attempt to improve run-time performance or optimize code must start with profiling the code by measuring its run-time through timing measurements via instrumentation. Lesson 6.134 – Measure Run-Time Performance of R Code demonstrates different methods for profiling code.

If an attempted optimization does not yield measurable and material reduction in run-time and the optimization resulted in less readable and less maintainable code, then the optimization should be rolled back. Readability, correctness, and maintainability are paramount.

Summary of Techniques

These techniques should generally be tried, in this general order:

  1. replace searching via loops with which() and any()
  2. use integers for lookup values (keys) rather than strings/text
  3. use apply() instead of loops
  4. use vectorized operations instead of loops
  5. avoid sqldf unless no simple alternatives exist
  6. avoid regular expressions or substring searches whenever possible
  7. prefer data.table over data frames
  8. pre-allocate memory when possible
  9. employ parallel processing
  10. incorporate C++
  11. save large objects

In the next section, we will look at the above strategies in more detail and using examples.

Throwing Money at the Problem

Of course, a common “business approach” to performance optimization is to “throw iron at the problem”, i.e., to purchase a computer with a more powerful CPU, more memory, a GPU, and perhaps a Neural Processor – or to spin up a more powerful virtual machine with a cloud provider. It might cost a lot of money, but it may be less than having a programmer spend time improving the code (and perhaps introducing bugs) – it may be a “quick fix” but it may be the right approach in many situations.

Performance Improvement Approaches

This section provides specific strategies for improving the performance of R code by actually tweaking the code or rewriting it in a different – and more economical – way. They are presented in order of complexity, starting with the least complex. Naturally, not all strategies are necessary at all times and some of the later approaches may not be worth the complexity introduced into the code. Remember that readability and maintainability are also important, not just performance.

1. Avoid Loops

Loops are a fundamental construct in programming, allowing for repeated execution of a block of code. However, in languages like R and Python, loops can be significantly slower compared to languages like Java and C++. This slowness is due to several factors, including the interpreted nature of these languages, the overhead of dynamic typing, and the way memory management is handled. Understanding the limitations of loops in R and Python, and knowing how to use alternatives like the apply family of functions in R, can help improve performance.

In R, loops are typically slower because each iteration involves interpretation overhead, dynamic type checking, and memory management tasks. This can become a bottleneck, especially when dealing with large datasets or performing complex computations within the loop. For instance, consider the following example of a simple loop in R that calculates the square of each element in a vector:

n <- 1e6 # number of iterations

# pre-allocate memory for result
result <- numeric(n)

for (i in 1:n) {
  result[i] <- i^2
}

In this code, the loop iterates one million times, and in each iteration, it performs an arithmetic operation and assigns the result to a vector. This repeated execution can be inefficient, as the interpreter handles each iteration individually, leading to increased execution time. It may take several seconds to execute. If you want to run the code for yourself and you have a fast CPU, then increase the limit for n to a billion or more. By the way, notice that the result vector result is pre-allocated to n elements rather than growing it dynamically. This is another common performance improvement and discussed in more detail later in this section.

To mitigate the poor performance of loops, R provides a family of apply functions, which are designed to perform operations on elements of data structures like arrays, matrices, and data frames in a more efficient manner. The apply functions are internally optimized and can reduce the overhead associated with loops. For instance, the sapply function can be used to achieve the same result as the loop above, but more efficiently:

# Using sapply to square each element in a vector
n <- 1e6
result <- sapply(1:n, function(x) x^2)

In this example, sapply applies the function function(x) x^2 to each element of the vector 1:n. The sapply function is typically faster than a loop because it is internally optimized to handle vectorized operations more efficiently.

Another member of the apply family is lapply, which is similar to sapply but returns a list instead of a vector. This can be useful when the result of the function applied is not necessarily of the same length or type as the input. For example:

# Using lapply to create a list of squared numbers
n <- 1e6
result <- lapply(1:n, function(x) x^2)

While lapply returns a list, it can still be more efficient than a traditional loop due to its optimized implementation.

For operations on matrices, the apply function can be particularly useful. It allows you to apply a function to the rows or columns of a matrix without explicitly writing loops. Here’s an example where apply is used to calculate the row sums of a matrix:

# Creating a matrix
mat <- matrix(1:1e6, nrow = 1e3, ncol = 1e3)

# Using apply to calculate row sums
row_sums <- apply(mat, 1, sum)

In this example, apply takes three arguments: the matrix mat, the margin (1 for rows, 2 for columns), and the function to apply (in this case, sum). The apply function efficiently iterates over the rows of the matrix and calculates their sums.

Moreover, R provides specialized functions like colSums, rowSums, colMeans, and rowMeans for common operations on matrices, which are even more efficient than using apply. For example:

# Using rowSums to calculate row sums
row_sums <- rowSums(mat)

These specialized functions are highly optimized and should be preferred over apply for their respective operations.

To summarize, while loops in R can be slow due to the interpreted nature of the language and the overhead of dynamic typing and memory management, using the apply family of functions can significantly improve performance. The apply functions are internally optimized to handle operations on data structures more efficiently, reducing the execution time compared to traditional loops. Understanding and leveraging these functions is crucial for writing efficient R code, especially when dealing with large datasets or complex computations.

Even when the use of the apply() functions results in better performance, some programmers might find loops more intuitive especially when coming from a procedural language such as C++. Therefore, a first implementation of an algorithm might use loops. Only once the code is running correctly, do some programmers transition to the use of the apply() functions. Of course, as one becomes more familiar with R, code follows more of the natural R programming idioms.

2. Use which()

Rather than looping through a vector or a column in a data frame, use the which() function (and its existential counterpart any()) as it is much faster. The code below demonstrates this when searching a vector for the position of a particular value (finds the first occurrence only):

n <- 1e8      # size of vector

# vector of random integer values
v <- round(runif(n, min = 100, max = n*n),0)

x <- 445876   # value to find
k <- 0        # position at which found

# insert value at a last position to ensure it is present
v[n] <- x

Now, let’s try to find the position of the key value x in the vector v. We will measure the run-time performance of both approaches (of course, on your computer the random values in v and the timings will be different).

Approach I: Linear Search with Loops

bt <- Sys.time()

for (i in 1:n) {
  if (x == v[i]) {
    k <- i
    break
  }
}

et <- Sys.time()

t.I <- et - bt

cat("Approach I / Loop: found ", x, "at position", k, "in", round((t.I),3), "seconds")
## Approach I / Loop: found  445876 at position 100000000 in 3.016 seconds

Approach II: Using which()

The approach below uses the which() function; as you can see it is substantially faster than looping.

bt <- Sys.time()

k <- which(x == v)

et <- Sys.time()

t.II <- et - bt

cat("Approach II / which: found ", x, "at position", k, "in", round((t.II),3), "seconds")
## Approach II / which: found  445876 at position 100000000 in 0.34 seconds

The difference in time is quite pronounced – about a 10x improvement in speed.

Of course, if the values in the vector had been sorted, then a binary search would have been substantially faster (complexity of \(O(log_n)\) vs \(O(n)\)). And, placing the values into a hashmap rather than a linear vector would also make search faster (\(O(1)\)) – however, R does not have built-in support for hashmaps, so mechanisms such as an in-memory key-value database (e.g., memcached) are often used.

Quick Tutorial: which()

The which() function in R is an efficient mechanism for identifying the indices of elements in a logical vector that meet a specified condition. It is often used as an alternative to loops for conditional searches, providing a more concise and typically faster way to accomplish such tasks. Recall that a column in a data frame is a vector, so this also can be used to search columns of data frames.

The which() function returns the positions in a vector where an element in the vector meets a logical condition. Essentially, it scans through a logical vector and identifies the positions where the condition is met.

Consider a simple example where we want to find the positions (indices) of elements in a numeric vector that are greater than a specified value. In this example, which(vec > 5) returns the indices of vec where the elements are greater than 5.

# Create a numeric vector
vec <- c(2, 4, 6, 8, 10, 3, 5, 7, 9)

# Use which() to find positions of elements greater than 5
indices <- which(vec > 5)

print(indices)
## [1] 3 4 5 8 9

The which() function is also useful for identifying rows in a data frame that meet certain conditions. Let’s consider a data frame example:

# Create a data frame
df <- data.frame(
  ID = 1:10,
  Score = c(85, 90, 88, 78, 92, 95, 70, 65, 88, 91)
)

# se which() to find rows where Score is greater than 90
rows <- which(df$Score > 90)

print(rows)
## [1]  5  6 10

Often, you want to subset the original vector or data frame based on the indices returned by which(). Here’s how you can do it:

# select rows in the data frame based on condition in a column
df.subset <- df[which(df$Score > 90), ]

head(df.subset)
##    ID Score
## 5   5    92
## 6   6    95
## 10 10    91

The which() function is more efficient than loops for identifying indices that meet a condition, as it leverages internal optimizations. Using which() makes the code more concise and readable compared to writing explicit loops – if one is used to R. However, it is the natural and idiomatic way to program in R.

3. Use Integer Keys

Keys should be integers whenever possible rather than character strings as comparing integers is much faster than comparing text strings (which are sequences of characters that have to be compared one character at a time). Of course, using a hash function to map strings to integers would be a good alternative. The code below compares the time to search an integer column versus a text column.

n <- 1e7

df <- data.frame(
  ID = round(runif(n, min = 1000, max = 100000),0),
  Score = round(runif(n, min = 40, max = 99),0)
)

# embed lookup value in the last row
lookup.value.int <- 445632
df$ID[nrow(df)] <- lookup.value.int

# add a text column
df$NUID <- as.character(df$ID)
lookup.value.chr <- as.character(lookup.value.int)
df$NUID[nrow(df)] <- lookup.value.chr

Integer Key Search:

bt <- Sys.time()

# lookup score based on ID
k <- df$Score[which(df$ID == lookup.value.int)]

et <- Sys.time()

t.integer <- et - bt

cat("Integer Key:", round((t.integer),3), "seconds")
## Integer Key: 0.035 seconds

Text/Character Key Search:

bt <- Sys.time()

# lookup score based on ID
k <- df$Score[which(df$NUID == lookup.value.chr)]

et <- Sys.time()

t.text <- et - bt

cat("Text Key:", round((t.text),3), "seconds")
## Text Key: 0.197 seconds

The lookup of a character key is 10x slower. Although, to be fair, it is quite fast when using which(). Try writing the same code with a loop for comparison. What do you notice? What is the performance difference?

4. Leverage Efficient Data Manipulation Packages

One of the primary ways to enhance performance is through efficient data manipulation. Data frames in R are versatile, but they may not always be the best choice for performance-critical applications. Instead, consider using the data.table package, which offers an enhanced version of data frames. Data tables are designed for fast aggregation, joining, and in-place updates. They also consume less memory and execute operations more quickly due to their optimized internal structure.

For example, suppose you have a large dataset and need to perform frequent subsetting and aggregations. Using data.table can significantly reduce execution time. Here is a demonstration:

Using a Data Frame:

# Creating a large data frame
df <- data.frame(x = rnorm(1e8), 
                 y = rnorm(1e8))

# Subsetting and aggregation
system.time({
  result <- mean(df$y[which(df$x > 0)])
})
##    user  system elapsed 
##   0.921   0.210   1.131

Using a data.table:

library(data.table)

# Creating a large data table
dt <- data.table(x = rnorm(1e8), 
                 y = rnorm(1e8))

# Subsetting and aggregation
system.time({
  result <- dt[x > 0, .(mean_y = mean(y))]
})
##    user  system elapsed 
##   1.045   0.142   1.210

In this example, data.table processes the subsetting and aggregation a bit faster than a regular data frame, making it ideal for large-scale data analysis, particularly when there are many columns.

5. Vectorize Operations

Vectorization is another critical technique for improving performance. R is inherently a vectorized language, meaning it can operate on entire vectors of data at once. By leveraging vectorized operations, you can avoid the overhead of explicit loops, which are often slow in R. For instance, instead of using a loop to add two vectors element-wise, you can directly use vectorized addition:

# Vectorized addition
a <- rnorm(1e7)
b <- rnorm(1e7)

system.time({
  c <- sum(a + b)
})
##    user  system elapsed 
##   0.032   0.000   0.032

Here, the vectorized addition is not only more concise but also much faster than looping through each element as demonstrated with the loop-based code below:

# Vectorized addition
a <- rnorm(1e7)
b <- rnorm(1e7)
c <- 0

system.time({
  for (i in 1:length(a)) {
    c <- c + (a[i] + b[i])
  }
})
##    user  system elapsed 
##   0.393   0.000   0.395

6. Preallocate Memory

Memory management is another aspect where performance can be improved. R’s garbage collector handles memory allocation and deallocation automatically, but inefficient memory usage can still slow down your code. Pre-allocating memory for large objects can prevent unnecessary memory reallocation during execution. For example, if you are appending elements to a vector inside a loop, it is better to pre-allocate the vector’s size than growing the vector dynamically as new elements are inserted.

In the code below, the initial vector is created empty; as new elements are inserted, R automatically allocates memory. Generally, this means that memory for a new vector with a size one element larger than the original vector is allocated and then the original vector’s elements are copied to the new vector.

# dynamically growing a vector
n <- 1e7
v <- numeric(0)

system.time({
  for (i in 1:n) {
    v[i] <- rnorm(1)
  }
})
##    user  system elapsed 
##  17.162   2.208  19.382

The code below pre-allocates the memory. Of course, this only works when the required number of elements is known beforehand. If it is not known, then the memory must be estimated, making certain not to overallocate.

# pre-allocating memory for a vector
n <- 1e7
v <- numeric(n)

system.time({
  for (i in 1:n) {
    v[i] <- rnorm(1)
  }
})
##    user  system elapsed 
##  14.771   1.882  16.861

This approach avoids the overhead associated with dynamically growing the vector. The effect becomes more pronounced over time.

7. Parallelize Processing

Parallel computing can also significantly reduce computation time for tasks that can be parallelized. R offers several packages for parallel processing, such as parallel, foreach, and future. The parallel package, for instance, provides functions to execute code on multiple CPU cores simultaneously. Of course, the more cores a CPU has, the better.

Here’s an example using the mclapply function:

library(parallel)

# Parallel processing using mclapply
system.time({
  result <- mclapply(1:8, function(x) {
    sum(rnorm(1e6))
  }, mc.cores = 4)
})
##    user  system elapsed 
##   0.002   0.017   0.113

In this example, the computation is distributed across four cores, resulting in a substantial decrease in execution time compared to a single-threaded approach.

8. Profile Code

Profiling your code is an essential step in identifying performance bottlenecks. The profvis package in R provides a graphical interface for profiling, allowing you to visualize where your code spends the most time. By pinpointing these hotspots, you can focus your optimization efforts more effectively.

library(profvis)

# Profiling code execution
profvis({
  result <- sapply(1:1e6, function(x) x^2)
})

This profiling tool helps you understand the time complexity of different code sections, guiding you towards targeted improvements.

8. Leverage GenAI

Generative AI assistants, such as ChatGPT, Co-Pilot, and Claude, can be quite valuable in identifying and resolving performance issues in R code. These AI systems can assist both novice and experienced programmers by providing insights, code reviews, optimization suggestions, and educational resources. Let’s explore some ways these AI assistants can be leveraged to improve the performance of R code.

One of the primary ways generative AI assistants can help is by reviewing your R code and suggesting optimizations. You can input sections of your code and ask the AI to analyze it for potential performance bottlenecks. For example, if you have a piece of code that involves loops or inefficient data manipulations, the AI can suggest more efficient alternatives, such as vectorized operations or the use of the data.table package.

Consider the following example where an AI assistant is asked to optimize a loop with the following prompt followed by pasting the code:

Optimize the following R code for performance:

# Loop to calculate cumulative sum
n <- 1e6
result <- numeric(n)
for (i in 1:n) {
  result[i] <- sum(1:i)
}

Below is the actual output for ChatGPT 4o (with some edits for brevity and formatting). Notice the explanations giving a novice programmer an opportunity to learn.

The provided R code calculates the cumulative sum using a loop, which can be optimized for better performance. Using vectorized operations, which are inherently faster in R, can significantly improve the efficiency of this code. Specifically, the `cumsum` function in R is designed for such tasks and is much more efficient than a loop.

Here's how you can optimize the code:

```r
n <- 1e6
result <- cumsum(1:n)
```

1.  **Vectorization**: The `cumsum` function calculates the cumulative sum of a numeric vector in a vectorized manner. This means that the computation is performed in an optimized way internally, avoiding the overhead of an explicit loop.

2.  **Avoiding Loops**: Loops in R, especially over large vectors, can be slow due to the interpreted nature of R and the overhead associated with repeatedly calling R functions. By using `cumsum`, you leverage highly optimized internal C code.

To demonstrate the performance improvement, we can compare the execution time of both the loop-based approach and the vectorized approach:

```r
n <- 1e6
result_loop <- numeric(n)
system.time({
  for (i in 1:n) {
    result_loop[i] <- sum(1:i)
  }
})

system.time({
  result_cumsum <- cumsum(1:n)
})
```

The explanation of code changes means that Generative AI can also be a teacher and coach. It can explain best practices for writing efficient R code, including providing guidance on vectorization, memory management, and the use of parallel computing. For example, an AI assistant can explain how to use the parallel package to speed up computations.

Naturally, not all suggestions might be correct – AI assistants do have a (deserved) reputation for writing incorrect code or getting their math wrong, so it is important to double-check all suggestions and to be a critical consumer of AI suggestions: caveat emptor as they used to say in Rome.

Generative AI assistants be particularly helpful in interactive debugging sessions, where you iteratively refine your code based on the AI’s feedback. You can describe the performance issues you’re encountering, and the AI will often suggest modifications and further optimizations. This iterative process helps in progressively improving the code’s performance.

9. Incorporate C++

Integrating C++ code into R can significantly enhance performance for critical sections of code, particularly when dealing with computationally intensive tasks. R, while powerful for data analysis and statistical computing, is not as fast as low-level languages like C++ due to its interpreted nature and dynamic typing. By offloading performance-critical tasks to C++, you can leverage the speed and efficiency of compiled code while maintaining the convenience of R for data manipulation and visualization. This approach is facilitated by the Rcpp package, which provides a seamless interface between R and C++.

R Notebooks allow code blocks in various languages and thus an R Notebook can be a mix of languages. The programmer can choose the “right language” for a programming task. In R scripts, C++ code can be wrapped around the function cppFunction() from the Rcpp package.

C++ is a compiled language and executes much faster than R, especially for loops and complex computations. In addition, C++ allows for more efficient memory management and can handle large datasets or complex algorithms more effectively. So, using C++ for performance-critical sections of code while utilizing R’s rich ecosystem for data manipulation and analysis provides a balanced approach that leverages each language’s strength.

To begin using C++ in R, you need to install the Rcpp package. This package allows for easy integration of C++ code within R scripts and functions.

The Rcpp package provides several functions to facilitate the integration of C++ code. One of the most commonly used functions is cppFunction, which allows you to define and compile a C++ function directly in your R script.

Consider a simple example where we want to compute the sum of squares of a numeric vector. Here is how you can implement this in C++ using Rcpp. Note how the C++ code is an argument to an R function which will compile the C++ code using an installed C++ compiler and then create a binding to allow the C++ function to be called from R.

The function cppFunction() calls the C++ compiler, compiles the code (which can take some time), and then creates a language binding so the compiled C++ function can be called from R.

C++ Function:

library(Rcpp)

cppFunction('
double sumOfSquares(NumericVector x) {
  int n = x.size();
  double sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += x[i] * x[i];
  }
  return sum;
}')

Using the C++ Function in R:

# Creating a numeric vector
vec <- rnorm(1e6)

# Calling the C++ function from R
result <- sumOfSquares(vec)
print(result)
## [1] 1001364

In this example, the C++ function sumOfSquares computes the sum of squares of the elements in the input vector x. This function is then called from R, demonstrating the seamless integration of R and C++. Writing more complex C++ code is best done by writing an entire package in C++ but that is beyond the scope of this lesson.

For a more complex example, consider matrix multiplication, a computationally intensive task that can benefit greatly from C++ optimization.

C++ Function for Matrix Multiplication:

cppFunction('
NumericMatrix matMult(NumericMatrix A, NumericMatrix B) {
  int n = A.nrow();
  int k = A.ncol();
  int m = B.ncol();
  NumericMatrix C(n, m);
  
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int l = 0; l < k; ++l) {
        C(i,j) += A(i,l) * B(l,j);
      }
    }
  }
  return C;
}')

Using the C++ Function in R:

# create two large matrices
A <- matrix(rnorm(1e6), nrow = 1000)
B <- matrix(rnorm(1e6), nrow = 1000)

# perform matrix multiplication using the C++ function
result <- matMult(A, B)

In this example, the matMult function multiplies two matrices A and B. The C++ implementation is significantly faster than a pure R implementation, especially for large matrices.

10. Save Large Objects

In R, you can save any data object, such as a data frame, to an R object file (.RData) using the save() function and then restore it using the load() function. This approach is useful for preserving the state of your data between sessions, especially when working with large datasets that require significant processing time. It means that you create the data object once, save it to an object file, and then restore it from the file when needed rather than cre-creating it.

First, create a data frame, then save the data frame to an R object file using the save function. When needed later in a new session, check if the object exists and, if not, load it. Before restoring the data frame, check if the object file exists. If the file exists, load the data frame using the load function, otherwise create the data frame. The code below demonstrates this.

# load the data
df.txns <- read.csv('customertxndata.csv')

### do some intensive processing that take significant time
### ...

# save the data frame to an R object file
save(df.txns, file = "df_txnData.RData")

### for testing we will remove the object from memory
rm(df.txns)

The code below checks if the object file exists, and, if it doesn’t, restores the data frame from the object file. Notice that the object file contains the data frame’s name as well.

# file path and name of the object file
file_path <- "df_txnData.RData"

# restore the data frame from its file -- if it exists
if (file.exists(file_path)) {
  load(file_path)
} else {
  # create the data frame
  # ...
}

# display the first few rows of the restored data frame
head(df.txns, 3)
##   NumVisits NumOrders      OS Gender    Total
## 1         7         0 Android   Male   0.0000
## 2        20         1     iOS   <NA> 576.8668
## 3        22         1     iOS Female 850.0000

Summary

In summary, optimizing R code performance involves a multifaceted approach. By adopting efficient data structures like data.table, leveraging vectorized operations, managing memory effectively, utilizing parallel computing, and profiling your code, you can achieve significant run-time improvements. These techniques are not only essential for handling large datasets but also for ensuring that your computations are both fast and scalable, an essential requirements for machine learning, statistical computing, and data applications.

The which() function in R is a highly efficient alternative to loops for conditional searches. It simplifies the process of identifying indices where a condition is met, providing both performance benefits and improved code readability. By leveraging which(), you can write more efficient and concise R code for tasks involving conditional subsetting and filtering.

Generative AI assistants like ChatGPT and Claude can be helpful in identifying and resolving performance issues in R code. For the critical programmer, they can provide code reviews, suggest optimizations, recommend efficient data structures, guide you through profiling techniques, and offer insights into best practices.

By integrating C++ code into R using the Rcpp package, you can achieve substantial performance improvements for computationally intensive tasks. This approach allows you to use R for data manipulation with the targeted efficiency of C++.

Files & Resources

All Files for Lesson 6.135

References

TBD

Errata

Let us know.

LS0tCnRpdGxlOiAiSW1wcm92aW5nIFJ1bi1UaW1lIFBlcmZvcm1hbmNlIG9mIFIgQ29kZSIKcGFyYW1zOgogIGNhdGVnb3J5OiA2CiAgbnVtYmVyOiAxMzUKICB0aW1lOiA0NQogIGxldmVsOiBiZWdpbm5lcgogIHRhZ3M6ICJSLGRlYnVnZ2luZyxydW50aW1lLHRpbWUsU3lzLnRpbWUsdGljdG9jLHJiZW5jaG1hcmsiCiAgZGVzY3JpcHRpb246ICJMaXN0cyBzZXZlcmFsIHdheXMgdG8gaW1wcm92ZSBhbmQgb3B0aW1pemUgdGhlCiAgICAgICAgICAgICAgICBydW4tdGltZSBwZXJmb3JtYW5jZSBvZiBSIGNvZGUuIERlbW9uc3RyYXRlcwogICAgICAgICAgICAgICAgc3RyYXRlZ2llcyB0aHJvdWdoIGV4YW1wbGVzLiIKZGF0ZTogIjxzbWFsbD5gciBTeXMuRGF0ZSgpYDwvc21hbGw+IgphdXRob3I6ICI8c21hbGw+TWFydGluIFNjaGVkbGJhdWVyPC9zbWFsbD4iCmVtYWlsOiAibS5zY2hlZGxiYXVlckBuZXUuZWR1IgphZmZpbGl0YXRpb246ICJOb3J0aGVhc3Rlcm4gVW5pdmVyc2l0eSIKb3V0cHV0OiAKICBib29rZG93bjo6aHRtbF9kb2N1bWVudDI6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgY29sbGFwc2VkOiBmYWxzZQogICAgbnVtYmVyX3NlY3Rpb25zOiBmYWxzZQogICAgY29kZV9kb3dubG9hZDogdHJ1ZQogICAgdGhlbWU6IHNwYWNlbGFiCiAgICBoaWdobGlnaHQ6IHRhbmdvCi0tLQoKLS0tCnRpdGxlOiAiPHNtYWxsPmByIHBhcmFtcyRjYXRlZ29yeWAuYHIgcGFyYW1zJG51bWJlcmA8L3NtYWxsPjxici8+PHNwYW4gc3R5bGU9J2NvbG9yOiAjMkU0MDUzOyBmb250LXNpemU6IDAuOWVtJz5gciBybWFya2Rvd246Om1ldGFkYXRhJHRpdGxlYDwvc3Bhbj4iCi0tLQoKYGBge3IgY29kZT14ZnVuOjpyZWFkX3V0ZjgocGFzdGUwKGhlcmU6OmhlcmUoKSwnL1IvX2luc2VydDJEQi5SJykpLCBpbmNsdWRlID0gRkFMU0V9CmBgYAoKIyMgSW50cm9kdWN0aW9uCgpJbXByb3ZpbmcgdGhlIHJ1bi10aW1lIHBlcmZvcm1hbmNlIG9mIFIgY29kZSBpcyBjcml0aWNhbCBmb3IgaGFuZGxpbmcgbGFyZ2UgZGF0YXNldHMgYW5kIGNvbXBsZXggY29tcHV0YXRpb25zLCBlc3BlY2lhbGx5IGluIG1hY2hpbmUgbGVhcm5pbmcsIGFwcGxpZWQgQUksIGRhdGEgbWluaW5nLCBhbmQgc3RhdGlzdGljYWwgYW5hbHlzaXMuIFRoaXMgbGVzc29uIGV4cGxvcmVzIHNldmVyYWwgYXBwcm9hY2hlcywgcmFuZ2luZyBmcm9tIG9wdGltaXppbmcgZGF0YSBzdHJ1Y3R1cmVzIHRvIHBhcmFsbGVsIGNvbXB1dGluZyB0ZWNobmlxdWVzLCB3aXRoIHRoZSBvYmplY3RpdmUgdG8gbWFrZSBSIGNvZGUgbW9yZSBlZmZpY2llbnQuCgpNYW55IG9mIHRoZSB0ZWNobmlxdWVzIHByZXNlbnRlZCBpbiB0aGlzIGxlc3NvbiBhcmUgdW5pdmVyc2FsbHkgYXBwbGljYWJsZSwgcGFydGljdWxhcmx5IHRvIG90aGVyIGludGVycHJldGVkIGxhbmd1YWdlcyBsaWtlIFB5dGhvbiBhbmQgSmF2YVNjcmlwdC4gVGhlIHJlbGF0aXZlIHNsb3duZXNzIG9mIFIgYW5kIFB5dGhvbiBjb21wYXJlZCB0byBsYW5ndWFnZXMgbGlrZSBKYXZhIGFuZCBDKysgY2FuIGJlIGF0dHJpYnV0ZWQgdG8gc2V2ZXJhbCBmYWN0b3JzIHJlbGF0ZWQgdG8gdGhlaXIgZGVzaWduIHBoaWxvc29waGllcywgcnVudGltZSBlbnZpcm9ubWVudHMsIGFuZCB0eXBpY2FsIHVzZSBjYXNlcy4gVW5kZXJzdGFuZGluZyB0aGVzZSBkaWZmZXJlbmNlcyBpcyBlc3NlbnRpYWwgd2hlbiBjaG9vc2luZyBhbiBhcHByb2FjaCB0byBjb2RlIG9wdGltaXphdGlvbi4KCkZpcnN0bHksIFIgYW5kIFB5dGhvbiBhcmUgaW50ZXJwcmV0ZWQgbGFuZ3VhZ2VzLCB3aGVyZWFzIEphdmEgYW5kIEMrKyBhcmUgY29tcGlsZWQgbGFuZ3VhZ2VzLiBJbiBpbnRlcnByZXRlZCBsYW5ndWFnZXMsIGNvZGUgaXMgZXhlY3V0ZWQgbGluZSBieSBsaW5lIGJ5IGFuIGludGVycHJldGVyIGF0IHJ1bnRpbWUsIHdoaWNoIGludHJvZHVjZXMgb3ZlcmhlYWQgYmVjYXVzZSB0aGUgaW50ZXJwcmV0ZXIgbmVlZHMgdG8gcGFyc2UgYW5kIGV4ZWN1dGUgZWFjaCBsaW5lIG9mIGNvZGUgZHluYW1pY2FsbHkuIEluIGNvbnRyYXN0LCBjb21waWxlZCBsYW5ndWFnZXMgbGlrZSBKYXZhIGFuZCBDKysgYXJlIHRyYW5zbGF0ZWQgaW50byBtYWNoaW5lIGNvZGUgYmVmb3JlIGV4ZWN1dGlvbiwgYWxsb3dpbmcgdGhlIENQVSB0byBydW4gdGhlIGNvZGUgZGlyZWN0bHkgd2l0aG91dCB0aGUgb3ZlcmhlYWQgb2YgaW50ZXJwcmV0YXRpb24uIFRoaXMgY29tcGlsYXRpb24gc3RlcCBnZW5lcmFsbHkgcmVzdWx0cyBpbiBmYXN0ZXIgZXhlY3V0aW9uIHRpbWVzIGZvciBKYXZhIGFuZCBDKysgcHJvZ3JhbXMuCgpSIGFuZCBQeXRob24gYXJlIGFsc28gZHluYW1pY2FsbHkgdHlwZWQgbGFuZ3VhZ2VzLiBUaGlzIG1lYW5zIHRoYXQgdHlwZSBjaGVja2luZyBoYXBwZW5zIGF0IHJ1bnRpbWUgcmF0aGVyIHRoYW4gYXQgY29tcGlsZSB0aW1lLiBXaGlsZSB0aGlzIHByb3ZpZGVzIGdyZWF0ZXIgZmxleGliaWxpdHkgYW5kIGVhc2Ugb2YgdXNlLCBpdCBpbmN1cnMgYWRkaXRpb25hbCBvdmVyaGVhZCBiZWNhdXNlIHRoZSBpbnRlcnByZXRlciBtdXN0IG1hbmFnZSB0eXBlIGluZm9ybWF0aW9uIGFuZCBwZXJmb3JtIHR5cGUgY2hlY2tpbmcgZHVyaW5nIGV4ZWN1dGlvbi4gSmF2YSBhbmQgQysrLCBiZWluZyBzdGF0aWNhbGx5IHR5cGVkIGxhbmd1YWdlcywgcGVyZm9ybSB0eXBlIGNoZWNraW5nIGF0IGNvbXBpbGUgdGltZSwgd2hpY2ggaGVscHMgb3B0aW1pemUgdGhlIGdlbmVyYXRlZCBtYWNoaW5lIGNvZGUgZm9yIGJldHRlciBwZXJmb3JtYW5jZS4KCkFub3RoZXIgc2lnbmlmaWNhbnQgZmFjdG9yIGZvciB0aGUgcG9vcmVyIHJ1bi10aW1lIHBlcmZvcm1hbmNlIG9mIFIgYW5kIFB5dGhvbiBhcmUgaW4gdGhlIHdheSBib3RoIG1hbmFnZSBtZW1vcnkuIFIgYW5kIFB5dGhvbiB1c2UgYXV0b21hdGljIGdhcmJhZ2UgY29sbGVjdGlvbiB0byBtYW5hZ2UgbWVtb3J5LCB3aGljaCBwZXJpb2RpY2FsbHkgZnJlZXMgdXAgbWVtb3J5IHRoYXQgaXMgbm8gbG9uZ2VyIGluIHVzZS4gV2hpbGUgdGhpcyBzaW1wbGlmaWVzIG1lbW9yeSBtYW5hZ2VtZW50IGZvciB0aGUgcHJvZ3JhbW1lciwgaXQgY2FuIGNhdXNlIHVucHJlZGljdGFibGUgcGF1c2VzIGluIHByb2dyYW0gZXhlY3V0aW9uIGFzIHRoZSBnYXJiYWdlIGNvbGxlY3RvciBydW5zLiBKYXZhIGFsc28gdXNlcyBnYXJiYWdlIGNvbGxlY3Rpb24gYnV0IGJlbmVmaXRzIGZyb20gbW9yZSBhZHZhbmNlZCBhbmQgb3B0aW1pemVkIGdhcmJhZ2UgY29sbGVjdGlvbiBhbGdvcml0aG1zIGNvbXBhcmVkIHRvIHRob3NlIHR5cGljYWxseSBmb3VuZCBpbiBSIGFuZCBQeXRob24uIEMrKywgb24gdGhlIG90aGVyIGhhbmQsIHJlcXVpcmVzIG1hbnVhbCBtZW1vcnkgbWFuYWdlbWVudCBieSB0aGUgcHJvZ3JhbW1lciwgd2hpY2ggYWZmb3JkcyBmdWxsIGNvbnRyb2wgb3ZlciBtZW1vcnkgYWxsb2NhdGlvbiBhbmQgZGVhbGxvY2F0aW9uLiBUaGlzIHByb2dyYW1tZXItZHJpdmVuIGFwcHJvYWNoIGFsbG93cyBmb3IgaGlnaGx5IG9wdGltaXplZCBtZW1vcnkgdXNhZ2UgYnV0IHJlcXVpcmVzIGNhcmVmdWwgcHJvZ3JhbW1pbmcgdG8gYXZvaWQgbWVtb3J5IGxlYWtzIGFuZCBvdGhlciBpc3N1ZXMuCgpUaGUgc3RhbmRhcmQgbGlicmFyaWVzIGFuZCBkYXRhIHN0cnVjdHVyZXMgcHJvdmlkZWQgYnkgUiBhbmQgUHl0aG9uIGFyZSBkZXNpZ25lZCBmb3IgZWFzZSBvZiB1c2UgYW5kIGZsZXhpYmlsaXR5IHJhdGhlciB0aGFuIHJhdyBwZXJmb3JtYW5jZS4gRm9yIGV4YW1wbGUsIFB5dGhvbidzIGxpc3QgYW5kIGRpY3Rpb25hcnkgb2JqZWN0cyBhcmUgaGlnaGx5IGZsZXhpYmxlIGJ1dCBub3QgYXMgZWZmaWNpZW50IGFzIEphdmEncyBvciBDKysncyBhcnJheSBhbmQgaGFzaCB0YWJsZSBpbXBsZW1lbnRhdGlvbnMuIFNpbWlsYXJseSwgUidzIGRhdGEgZnJhbWUgYW5kIGxpc3Qgc3RydWN0dXJlcyBwcmlvcml0aXplIGNvbnZlbmllbmNlIGFuZCBlYXNlIG9mIG1hbmlwdWxhdGlvbiBvdmVyIHBlcmZvcm1hbmNlLiBJbiBjb250cmFzdCwgSmF2YSBhbmQgQysrIHN0YW5kYXJkIGxpYnJhcmllcyBhcmUgb2Z0ZW4gZGVzaWduZWQgd2l0aCBwZXJmb3JtYW5jZSBpbiBtaW5kLCBwcm92aWRpbmcgbW9yZSBlZmZpY2llbnQgZGF0YSBzdHJ1Y3R1cmVzIGFuZCBhbGdvcml0aG1zLiBJbiBmYWN0LCBtYW55IG9mIHRoZSBoaWdoLXBlcmZvcm1hbmNlIGZ1bmN0aW9ucyBpbiB0aGlyZC1wYXJ0eSBwYWNrYWdlcyBmb3IgUiBhbmQgUHl0aG9uIGFyZSB3cml0dGVuIGluIEMrKyBvciBKYXZhLgoKUiBhbmQgUHl0aG9uIGFyZSBhbHNvIGhlYXZpbHkgdXNlZCBpbiBkYXRhIGFuYWx5c2lzLCBzY2llbnRpZmljIGNvbXB1dGluZywgYW5kIG1hY2hpbmUgbGVhcm5pbmcsIHdoZXJlIHRoZSBlYXNlIG9mIHByb3RvdHlwaW5nIGFuZCB0aGUgYXZhaWxhYmlsaXR5IG9mIGV4dGVuc2l2ZSBsaWJyYXJpZXMgKHN1Y2ggYXMgTnVtUHksIHBhbmRhcywgYW5kIHNjaWtpdC1sZWFybiBpbiBQeXRob24sIGFuZCBjYXJldCwgcHN5Y2gsIGRhdGEudGFibGUgYW5kIGdncGxvdDIgaW4gUikgYXJlIG1vcmUgY3JpdGljYWwgdGhhbiByYXcgZXhlY3V0aW9uIHNwZWVkLiBUaGVzZSBsYW5ndWFnZXMgb2Z0ZW4gc2VydmUgYXMgImdsdWUiIGxhbmd1YWdlcywgd2hlcmUgcGVyZm9ybWFuY2UtY3JpdGljYWwgcGFydHMgb2YgdGhlIGNvZGUgYXJlIGltcGxlbWVudGVkIGluIG1vcmUgZWZmaWNpZW50IGxhbmd1YWdlcyBsaWtlIEMgb3IgQysrIGFuZCB0aGVuIGNhbGxlZCBmcm9tIFIgb3IgUHl0aG9uLiBUaGlzIGFwcHJvYWNoIGxldmVyYWdlcyB0aGUgc3RyZW5ndGhzIG9mIGJvdGggaGlnaC1sZXZlbCBhbmQgbG93LWxldmVsIGxhbmd1YWdlcy4gSXQgaXMgbm90IHVudXN1YWwgZm9yIGV4cGxvcmF0aW9uIGFuZCByZXNlYXJjaCB0byBiZSBkb25lIGluIFIgYW5kIFB5dGhvbiBhbmQgdGhlbiwgb25jZSBhbiBhcHByb2FjaCBpcyBzZXR0bGVkIHVwb24sIHRoZSBjb2RlIGlzIHJld3JpdHRlbiBmb3IgcGVyZm9ybWFuY2UgaW4gSmF2YSBvciBDKysuIEluIGZhY3QsIFIgTm90ZWJvb2tzIGFsbG93IGNvZGUgY2h1bmtzIHRvIGJlIGluIFIsIFB5dGhvbiwgSmF2YSwgU1FMLCBhbmQgQysrIHdoaWNoIHByb3ZpZGVzIGZ1bGwgY29udHJvbCB0byB0aGUgcHJvZ3JhbW1lci4KCkZ1cnRoZXJtb3JlLCBSIGFuZCBQeXRob24gZW1waGFzaXplIHJlYWRhYmlsaXR5IGFuZCBlYXNlIG9mIHVzZSwgd2hpY2ggY2FuIHNvbWV0aW1lcyBsZWFkIHRvIGxlc3MgZWZmaWNpZW50IGNvZGUuIEZvciBleGFtcGxlLCBQeXRob24ncyB1c2Ugb2YgZHluYW1pYyB0eXBpbmcgYW5kIGhpZ2gtbGV2ZWwgZGF0YSBzdHJ1Y3R1cmVzIGVuY291cmFnZXMgYSBwcm9ncmFtbWluZyBzdHlsZSB0aGF0IG1heSBiZSBtb3JlIGludHVpdGl2ZSBidXQgbGVzcyBlZmZpY2llbnQuIEphdmEgYW5kIEMrKywgaW4gY29udHJhc3QsIGVuY291cmFnZSBtb3JlIGV4cGxpY2l0IGFuZCBvcHRpbWl6ZWQgcHJvZ3JhbW1pbmcgcHJhY3RpY2VzIGR1ZSB0byB0aGVpciBzdGF0aWNhbGx5IHR5cGVkIG5hdHVyZSBhbmQgbG93ZXItbGV2ZWwgY29udHJvbCBvdmVyIHN5c3RlbSByZXNvdXJjZXMuCgpMYXN0bHksIHRoZSBleGVjdXRpb24gbW9kZWwgb2YgdGhlc2UgbGFuZ3VhZ2VzIGRpZmZlcnMuIFIsIGZvciBleGFtcGxlLCBpcyBkZXNpZ25lZCBmb3Igc3RhdGlzdGljYWwgY29tcHV0aW5nIGFuZCBkYXRhIGFuYWx5c2lzLCB3aGVyZSB0eXBpY2FsIHdvcmtsb2FkcyBpbnZvbHZlIHZlY3Rvcml6ZWQgb3BlcmF0aW9ucyBhbmQgZGF0YSBtYW5pcHVsYXRpb24gdGFza3MgdGhhdCBjYW4gYmUgbW9yZSBlZmZpY2llbnRseSBoYW5kbGVkIGJ5IHNwZWNpYWxpemVkIGxpYnJhcmllcyB3cml0dGVuIGluIEMgb3IgZXZlbiAoZ29vZCBvbGQpIEZPUlRSQU4uIFB5dGhvbiwgd2hpbGUgbW9yZSBnZW5lcmFsLXB1cnBvc2UsIGlzIG9mdGVuIHVzZWQgaW4gc2ltaWxhciBkb21haW5zIGFuZCBiZW5lZml0cyBmcm9tIGV4dGVuc2l2ZSBDIGFuZCBDKysgZXh0ZW5zaW9ucyB0byBtaXRpZ2F0ZSBwZXJmb3JtYW5jZSBpc3N1ZXMuCgpJbiBzaG9ydCwgdGhlIHNsb3duZXNzIG9mIFIgYW5kIFB5dGhvbiBjb21wYXJlZCB0byBKYXZhIGFuZCBDKysgc3RlbXMgZnJvbSB0aGVpciBpbnRlcnByZXRlZCBuYXR1cmUsIGR5bmFtaWMgdHlwaW5nLCBtZW1vcnkgbWFuYWdlbWVudCBzdHJhdGVnaWVzLCBhbmQgZGVzaWduIHByaW9yaXRpZXMgdGhhdCBlbXBoYXNpemUgZWFzZSBvZiB1c2UgYW5kIGZsZXhpYmlsaXR5IG92ZXIgcmF3IHBlcmZvcm1hbmNlLiBVbmRlcnN0YW5kaW5nIHRoZXNlIHRyYWRlLW9mZnMgaXMgZXNzZW50aWFsIGZvciBzZWxlY3RpbmcgdGhlIHJpZ2h0IGxhbmd1YWdlIGZvciB5b3VyIHNwZWNpZmljIGFwcGxpY2F0aW9uIGFuZCBmb3IgbGV2ZXJhZ2luZyB0aGUgc3RyZW5ndGhzIG9mIGVhY2ggbGFuZ3VhZ2UgZWZmZWN0aXZlbHkuCgpBIGZpbmFsIHdvcmQgYW5kIGNhdXRpb246IEFuIGV4cGVyaWVuY2VkIHByb2dyYW1tZXIgYWx3YXlzIGJlZ2lucyBieSB3cml0aW5nIGNvcnJlY3QgY29kZSB0aGF0IGlzIHNpbXBsZSBhbmQgZWFzeSB0byBmb2xsb3cuIFJ1bi10aW1lIGlzIHNlY29uZGFyeSB0byBjb3JyZWN0bmVzcy4gT25seSBpZiB0aGUgcGVyZm9ybWFuY2Ugb2YgdGhlIGNvZGUgZG9lcyBub3QgbWVldCBlc3NlbnRpYWwgbm9uLWZ1bmN0aW9uYWwgcmVxdWlyZW1lbnRzLCBzaG91bGQgY2hhbmdlcyB0byB0aGUgY29kZSBiZSBlbnRlcnRhaW5lZC4gSW1wcm92ZW1lbnQgbXVzdCBwcm9jZWVkIGluIHN0YWdlcywgc3RhcnRpbmcgd2l0aCB0aGUgc2ltcGxlc3QgbW9kaWZpY2F0aW9ucy4KCiMjIE1lYXN1cmluZyBQZXJmb3JtYW5jZQoKQW55IGF0dGVtcHQgdG8gaW1wcm92ZSBydW4tdGltZSBwZXJmb3JtYW5jZSBvciBvcHRpbWl6ZSBjb2RlIG11c3Qgc3RhcnQgd2l0aCBwcm9maWxpbmcgdGhlIGNvZGUgYnkgbWVhc3VyaW5nIGl0cyBydW4tdGltZSB0aHJvdWdoIHRpbWluZyBtZWFzdXJlbWVudHMgdmlhIGluc3RydW1lbnRhdGlvbi4gTGVzc29uIFs2LjEzNCAtLSBNZWFzdXJlIFJ1bi1UaW1lIFBlcmZvcm1hbmNlIG9mIFIgQ29kZV0oaHR0cDovL2FydGlmaWNpdW0udXMvbGVzc29ucy8wNi5yL2wtNi0xMzQtcGVyZi1tZWFzdXJlLXIvbC02LTEzNC5odG1sKSBkZW1vbnN0cmF0ZXMgZGlmZmVyZW50IG1ldGhvZHMgZm9yIHByb2ZpbGluZyBjb2RlLgoKSWYgYW4gYXR0ZW1wdGVkIG9wdGltaXphdGlvbiBkb2VzIG5vdCB5aWVsZCBtZWFzdXJhYmxlIGFuZCBtYXRlcmlhbCByZWR1Y3Rpb24gaW4gcnVuLXRpbWUgYW5kIHRoZSBvcHRpbWl6YXRpb24gcmVzdWx0ZWQgaW4gbGVzcyByZWFkYWJsZSBhbmQgbGVzcyBtYWludGFpbmFibGUgY29kZSwgdGhlbiB0aGUgb3B0aW1pemF0aW9uIHNob3VsZCBiZSByb2xsZWQgYmFjay4gUmVhZGFiaWxpdHksIGNvcnJlY3RuZXNzLCBhbmQgbWFpbnRhaW5hYmlsaXR5IGFyZSBwYXJhbW91bnQuCgojIyBTdW1tYXJ5IG9mIFRlY2huaXF1ZXMKClRoZXNlIHRlY2huaXF1ZXMgc2hvdWxkIGdlbmVyYWxseSBiZSB0cmllZCwgaW4gdGhpcyBnZW5lcmFsIG9yZGVyOgoKMS4gIHJlcGxhY2Ugc2VhcmNoaW5nIHZpYSBsb29wcyB3aXRoIGB3aGljaCgpYCBhbmQgYGFueSgpYAoyLiAgdXNlIGludGVnZXJzIGZvciBsb29rdXAgdmFsdWVzIChrZXlzKSByYXRoZXIgdGhhbiBzdHJpbmdzL3RleHQKMy4gIHVzZSBgYXBwbHkoKWAgaW5zdGVhZCBvZiBsb29wcwo0LiAgdXNlIHZlY3Rvcml6ZWQgb3BlcmF0aW9ucyBpbnN0ZWFkIG9mIGxvb3BzCjUuICBhdm9pZCAqKnNxbGRmKiogdW5sZXNzIG5vIHNpbXBsZSBhbHRlcm5hdGl2ZXMgZXhpc3QKNi4gIGF2b2lkIHJlZ3VsYXIgZXhwcmVzc2lvbnMgb3Igc3Vic3RyaW5nIHNlYXJjaGVzIHdoZW5ldmVyIHBvc3NpYmxlCjcuICBwcmVmZXIgYGRhdGEudGFibGVgIG92ZXIgZGF0YSBmcmFtZXMKOC4gIHByZS1hbGxvY2F0ZSBtZW1vcnkgd2hlbiBwb3NzaWJsZQo5LiAgZW1wbG95IHBhcmFsbGVsIHByb2Nlc3NpbmcKMTAuIGluY29ycG9yYXRlIEMrKwoxMS4gc2F2ZSBsYXJnZSBvYmplY3RzCgpJbiB0aGUgbmV4dCBzZWN0aW9uLCB3ZSB3aWxsIGxvb2sgYXQgdGhlIGFib3ZlIHN0cmF0ZWdpZXMgaW4gbW9yZSBkZXRhaWwgYW5kIHVzaW5nIGV4YW1wbGVzLgoKIyMgVGhyb3dpbmcgTW9uZXkgYXQgdGhlIFByb2JsZW0KCk9mIGNvdXJzZSwgYSBjb21tb24gImJ1c2luZXNzIGFwcHJvYWNoIiB0byBwZXJmb3JtYW5jZSBvcHRpbWl6YXRpb24gaXMgdG8gInRocm93IGlyb24gYXQgdGhlIHByb2JsZW0iLCAqaS5lLiosIHRvIHB1cmNoYXNlIGEgY29tcHV0ZXIgd2l0aCBhIG1vcmUgcG93ZXJmdWwgQ1BVLCBtb3JlIG1lbW9yeSwgYSBHUFUsIGFuZCBwZXJoYXBzIGEgTmV1cmFsIFByb2Nlc3NvciAtLSBvciB0byBzcGluIHVwIGEgbW9yZSBwb3dlcmZ1bCB2aXJ0dWFsIG1hY2hpbmUgd2l0aCBhIGNsb3VkIHByb3ZpZGVyLiBJdCBtaWdodCBjb3N0IGEgbG90IG9mIG1vbmV5LCBidXQgaXQgbWF5IGJlIGxlc3MgdGhhbiBoYXZpbmcgYSBwcm9ncmFtbWVyIHNwZW5kIHRpbWUgaW1wcm92aW5nIHRoZSBjb2RlIChhbmQgcGVyaGFwcyBpbnRyb2R1Y2luZyBidWdzKSAtLSBpdCBtYXkgYmUgYSAicXVpY2sgZml4IiBidXQgaXQgbWF5IGJlIHRoZSByaWdodCBhcHByb2FjaCBpbiBtYW55IHNpdHVhdGlvbnMuCgojIyBQZXJmb3JtYW5jZSBJbXByb3ZlbWVudCBBcHByb2FjaGVzCgpUaGlzIHNlY3Rpb24gcHJvdmlkZXMgc3BlY2lmaWMgc3RyYXRlZ2llcyBmb3IgaW1wcm92aW5nIHRoZSBwZXJmb3JtYW5jZSBvZiBSIGNvZGUgYnkgYWN0dWFsbHkgdHdlYWtpbmcgdGhlIGNvZGUgb3IgcmV3cml0aW5nIGl0IGluIGEgZGlmZmVyZW50IC0tIGFuZCBtb3JlIGVjb25vbWljYWwgLS0gd2F5LiBUaGV5IGFyZSBwcmVzZW50ZWQgaW4gb3JkZXIgb2YgY29tcGxleGl0eSwgc3RhcnRpbmcgd2l0aCB0aGUgbGVhc3QgY29tcGxleC4gTmF0dXJhbGx5LCBub3QgYWxsIHN0cmF0ZWdpZXMgYXJlIG5lY2Vzc2FyeSBhdCBhbGwgdGltZXMgYW5kIHNvbWUgb2YgdGhlIGxhdGVyIGFwcHJvYWNoZXMgbWF5IG5vdCBiZSB3b3J0aCB0aGUgY29tcGxleGl0eSBpbnRyb2R1Y2VkIGludG8gdGhlIGNvZGUuIFJlbWVtYmVyIHRoYXQgcmVhZGFiaWxpdHkgYW5kIG1haW50YWluYWJpbGl0eSBhcmUgYWxzbyBpbXBvcnRhbnQsIG5vdCBqdXN0IHBlcmZvcm1hbmNlLgoKIyMjIDEuIEF2b2lkIExvb3BzCgpMb29wcyBhcmUgYSBmdW5kYW1lbnRhbCBjb25zdHJ1Y3QgaW4gcHJvZ3JhbW1pbmcsIGFsbG93aW5nIGZvciByZXBlYXRlZCBleGVjdXRpb24gb2YgYSBibG9jayBvZiBjb2RlLiBIb3dldmVyLCBpbiBsYW5ndWFnZXMgbGlrZSBSIGFuZCBQeXRob24sIGxvb3BzIGNhbiBiZSBzaWduaWZpY2FudGx5IHNsb3dlciBjb21wYXJlZCB0byBsYW5ndWFnZXMgbGlrZSBKYXZhIGFuZCBDKysuIFRoaXMgc2xvd25lc3MgaXMgZHVlIHRvIHNldmVyYWwgZmFjdG9ycywgaW5jbHVkaW5nIHRoZSBpbnRlcnByZXRlZCBuYXR1cmUgb2YgdGhlc2UgbGFuZ3VhZ2VzLCB0aGUgb3ZlcmhlYWQgb2YgZHluYW1pYyB0eXBpbmcsIGFuZCB0aGUgd2F5IG1lbW9yeSBtYW5hZ2VtZW50IGlzIGhhbmRsZWQuIFVuZGVyc3RhbmRpbmcgdGhlIGxpbWl0YXRpb25zIG9mIGxvb3BzIGluIFIgYW5kIFB5dGhvbiwgYW5kIGtub3dpbmcgaG93IHRvIHVzZSBhbHRlcm5hdGl2ZXMgbGlrZSB0aGUgYGFwcGx5YCBmYW1pbHkgb2YgZnVuY3Rpb25zIGluIFIsIGNhbiBoZWxwIGltcHJvdmUgcGVyZm9ybWFuY2UuCgpJbiBSLCBsb29wcyBhcmUgdHlwaWNhbGx5IHNsb3dlciBiZWNhdXNlIGVhY2ggaXRlcmF0aW9uIGludm9sdmVzIGludGVycHJldGF0aW9uIG92ZXJoZWFkLCBkeW5hbWljIHR5cGUgY2hlY2tpbmcsIGFuZCBtZW1vcnkgbWFuYWdlbWVudCB0YXNrcy4gVGhpcyBjYW4gYmVjb21lIGEgYm90dGxlbmVjaywgZXNwZWNpYWxseSB3aGVuIGRlYWxpbmcgd2l0aCBsYXJnZSBkYXRhc2V0cyBvciBwZXJmb3JtaW5nIGNvbXBsZXggY29tcHV0YXRpb25zIHdpdGhpbiB0aGUgbG9vcC4gRm9yIGluc3RhbmNlLCBjb25zaWRlciB0aGUgZm9sbG93aW5nIGV4YW1wbGUgb2YgYSBzaW1wbGUgbG9vcCBpbiBSIHRoYXQgY2FsY3VsYXRlcyB0aGUgc3F1YXJlIG9mIGVhY2ggZWxlbWVudCBpbiBhIHZlY3RvcjoKCmBgYHtyIGV2YWw9Rn0KbiA8LSAxZTYgIyBudW1iZXIgb2YgaXRlcmF0aW9ucwoKIyBwcmUtYWxsb2NhdGUgbWVtb3J5IGZvciByZXN1bHQKcmVzdWx0IDwtIG51bWVyaWMobikKCmZvciAoaSBpbiAxOm4pIHsKICByZXN1bHRbaV0gPC0gaV4yCn0KYGBgCgpJbiB0aGlzIGNvZGUsIHRoZSBsb29wIGl0ZXJhdGVzIG9uZSBtaWxsaW9uIHRpbWVzLCBhbmQgaW4gZWFjaCBpdGVyYXRpb24sIGl0IHBlcmZvcm1zIGFuIGFyaXRobWV0aWMgb3BlcmF0aW9uIGFuZCBhc3NpZ25zIHRoZSByZXN1bHQgdG8gYSB2ZWN0b3IuIFRoaXMgcmVwZWF0ZWQgZXhlY3V0aW9uIGNhbiBiZSBpbmVmZmljaWVudCwgYXMgdGhlIGludGVycHJldGVyIGhhbmRsZXMgZWFjaCBpdGVyYXRpb24gaW5kaXZpZHVhbGx5LCBsZWFkaW5nIHRvIGluY3JlYXNlZCBleGVjdXRpb24gdGltZS4gSXQgbWF5IHRha2Ugc2V2ZXJhbCBzZWNvbmRzIHRvIGV4ZWN1dGUuIElmIHlvdSB3YW50IHRvIHJ1biB0aGUgY29kZSBmb3IgeW91cnNlbGYgYW5kIHlvdSBoYXZlIGEgZmFzdCBDUFUsIHRoZW4gaW5jcmVhc2UgdGhlIGxpbWl0IGZvciAqbiogdG8gYSBiaWxsaW9uIG9yIG1vcmUuIEJ5IHRoZSB3YXksIG5vdGljZSB0aGF0IHRoZSByZXN1bHQgdmVjdG9yICpyZXN1bHQqIGlzIHByZS1hbGxvY2F0ZWQgdG8gKm4qIGVsZW1lbnRzIHJhdGhlciB0aGFuIGdyb3dpbmcgaXQgZHluYW1pY2FsbHkuIFRoaXMgaXMgYW5vdGhlciBjb21tb24gcGVyZm9ybWFuY2UgaW1wcm92ZW1lbnQgYW5kIGRpc2N1c3NlZCBpbiBtb3JlIGRldGFpbCBsYXRlciBpbiB0aGlzIHNlY3Rpb24uCgpUbyBtaXRpZ2F0ZSB0aGUgcG9vciBwZXJmb3JtYW5jZSBvZiBsb29wcywgUiBwcm92aWRlcyBhIGZhbWlseSBvZiBgYXBwbHlgIGZ1bmN0aW9ucywgd2hpY2ggYXJlIGRlc2lnbmVkIHRvIHBlcmZvcm0gb3BlcmF0aW9ucyBvbiBlbGVtZW50cyBvZiBkYXRhIHN0cnVjdHVyZXMgbGlrZSBhcnJheXMsIG1hdHJpY2VzLCBhbmQgZGF0YSBmcmFtZXMgaW4gYSBtb3JlIGVmZmljaWVudCBtYW5uZXIuIFRoZSBgYXBwbHlgIGZ1bmN0aW9ucyBhcmUgaW50ZXJuYWxseSBvcHRpbWl6ZWQgYW5kIGNhbiByZWR1Y2UgdGhlIG92ZXJoZWFkIGFzc29jaWF0ZWQgd2l0aCBsb29wcy4gRm9yIGluc3RhbmNlLCB0aGUgYHNhcHBseWAgZnVuY3Rpb24gY2FuIGJlIHVzZWQgdG8gYWNoaWV2ZSB0aGUgc2FtZSByZXN1bHQgYXMgdGhlIGxvb3AgYWJvdmUsIGJ1dCBtb3JlIGVmZmljaWVudGx5OgoKYGBge3IgZXZhbD1GfQojIFVzaW5nIHNhcHBseSB0byBzcXVhcmUgZWFjaCBlbGVtZW50IGluIGEgdmVjdG9yCm4gPC0gMWU2CnJlc3VsdCA8LSBzYXBwbHkoMTpuLCBmdW5jdGlvbih4KSB4XjIpCmBgYAoKSW4gdGhpcyBleGFtcGxlLCBgc2FwcGx5YCBhcHBsaWVzIHRoZSBmdW5jdGlvbiBgZnVuY3Rpb24oeCkgeF4yYCB0byBlYWNoIGVsZW1lbnQgb2YgdGhlIHZlY3RvciBgMTpuYC4gVGhlIGBzYXBwbHlgIGZ1bmN0aW9uIGlzIHR5cGljYWxseSBmYXN0ZXIgdGhhbiBhIGxvb3AgYmVjYXVzZSBpdCBpcyBpbnRlcm5hbGx5IG9wdGltaXplZCB0byBoYW5kbGUgdmVjdG9yaXplZCBvcGVyYXRpb25zIG1vcmUgZWZmaWNpZW50bHkuCgpBbm90aGVyIG1lbWJlciBvZiB0aGUgYGFwcGx5YCBmYW1pbHkgaXMgYGxhcHBseWAsIHdoaWNoIGlzIHNpbWlsYXIgdG8gYHNhcHBseWAgYnV0IHJldHVybnMgYSBsaXN0IGluc3RlYWQgb2YgYSB2ZWN0b3IuIFRoaXMgY2FuIGJlIHVzZWZ1bCB3aGVuIHRoZSByZXN1bHQgb2YgdGhlIGZ1bmN0aW9uIGFwcGxpZWQgaXMgbm90IG5lY2Vzc2FyaWx5IG9mIHRoZSBzYW1lIGxlbmd0aCBvciB0eXBlIGFzIHRoZSBpbnB1dC4gRm9yIGV4YW1wbGU6CgpgYGB7ciBldmFsPUZ9CiMgVXNpbmcgbGFwcGx5IHRvIGNyZWF0ZSBhIGxpc3Qgb2Ygc3F1YXJlZCBudW1iZXJzCm4gPC0gMWU2CnJlc3VsdCA8LSBsYXBwbHkoMTpuLCBmdW5jdGlvbih4KSB4XjIpCmBgYAoKV2hpbGUgYGxhcHBseWAgcmV0dXJucyBhIGxpc3QsIGl0IGNhbiBzdGlsbCBiZSBtb3JlIGVmZmljaWVudCB0aGFuIGEgdHJhZGl0aW9uYWwgbG9vcCBkdWUgdG8gaXRzIG9wdGltaXplZCBpbXBsZW1lbnRhdGlvbi4KCkZvciBvcGVyYXRpb25zIG9uIG1hdHJpY2VzLCB0aGUgYGFwcGx5YCBmdW5jdGlvbiBjYW4gYmUgcGFydGljdWxhcmx5IHVzZWZ1bC4gSXQgYWxsb3dzIHlvdSB0byBhcHBseSBhIGZ1bmN0aW9uIHRvIHRoZSByb3dzIG9yIGNvbHVtbnMgb2YgYSBtYXRyaXggd2l0aG91dCBleHBsaWNpdGx5IHdyaXRpbmcgbG9vcHMuIEhlcmXigJlzIGFuIGV4YW1wbGUgd2hlcmUgYGFwcGx5YCBpcyB1c2VkIHRvIGNhbGN1bGF0ZSB0aGUgcm93IHN1bXMgb2YgYSBtYXRyaXg6CgpgYGB7cn0KIyBDcmVhdGluZyBhIG1hdHJpeAptYXQgPC0gbWF0cml4KDE6MWU2LCBucm93ID0gMWUzLCBuY29sID0gMWUzKQoKIyBVc2luZyBhcHBseSB0byBjYWxjdWxhdGUgcm93IHN1bXMKcm93X3N1bXMgPC0gYXBwbHkobWF0LCAxLCBzdW0pCmBgYAoKSW4gdGhpcyBleGFtcGxlLCBgYXBwbHlgIHRha2VzIHRocmVlIGFyZ3VtZW50czogdGhlIG1hdHJpeCBgbWF0YCwgdGhlIG1hcmdpbiAoMSBmb3Igcm93cywgMiBmb3IgY29sdW1ucyksIGFuZCB0aGUgZnVuY3Rpb24gdG8gYXBwbHkgKGluIHRoaXMgY2FzZSwgYHN1bWApLiBUaGUgYGFwcGx5YCBmdW5jdGlvbiBlZmZpY2llbnRseSBpdGVyYXRlcyBvdmVyIHRoZSByb3dzIG9mIHRoZSBtYXRyaXggYW5kIGNhbGN1bGF0ZXMgdGhlaXIgc3Vtcy4KCk1vcmVvdmVyLCBSIHByb3ZpZGVzIHNwZWNpYWxpemVkIGZ1bmN0aW9ucyBsaWtlIGBjb2xTdW1zYCwgYHJvd1N1bXNgLCBgY29sTWVhbnNgLCBhbmQgYHJvd01lYW5zYCBmb3IgY29tbW9uIG9wZXJhdGlvbnMgb24gbWF0cmljZXMsIHdoaWNoIGFyZSBldmVuIG1vcmUgZWZmaWNpZW50IHRoYW4gdXNpbmcgYGFwcGx5YC4gRm9yIGV4YW1wbGU6CgpgYGB7cn0KIyBVc2luZyByb3dTdW1zIHRvIGNhbGN1bGF0ZSByb3cgc3Vtcwpyb3dfc3VtcyA8LSByb3dTdW1zKG1hdCkKYGBgCgpUaGVzZSBzcGVjaWFsaXplZCBmdW5jdGlvbnMgYXJlIGhpZ2hseSBvcHRpbWl6ZWQgYW5kIHNob3VsZCBiZSBwcmVmZXJyZWQgb3ZlciBgYXBwbHlgIGZvciB0aGVpciByZXNwZWN0aXZlIG9wZXJhdGlvbnMuCgpUbyBzdW1tYXJpemUsIHdoaWxlIGxvb3BzIGluIFIgY2FuIGJlIHNsb3cgZHVlIHRvIHRoZSBpbnRlcnByZXRlZCBuYXR1cmUgb2YgdGhlIGxhbmd1YWdlIGFuZCB0aGUgb3ZlcmhlYWQgb2YgZHluYW1pYyB0eXBpbmcgYW5kIG1lbW9yeSBtYW5hZ2VtZW50LCB1c2luZyB0aGUgYGFwcGx5YCBmYW1pbHkgb2YgZnVuY3Rpb25zIGNhbiBzaWduaWZpY2FudGx5IGltcHJvdmUgcGVyZm9ybWFuY2UuIFRoZSBgYXBwbHlgIGZ1bmN0aW9ucyBhcmUgaW50ZXJuYWxseSBvcHRpbWl6ZWQgdG8gaGFuZGxlIG9wZXJhdGlvbnMgb24gZGF0YSBzdHJ1Y3R1cmVzIG1vcmUgZWZmaWNpZW50bHksIHJlZHVjaW5nIHRoZSBleGVjdXRpb24gdGltZSBjb21wYXJlZCB0byB0cmFkaXRpb25hbCBsb29wcy4gVW5kZXJzdGFuZGluZyBhbmQgbGV2ZXJhZ2luZyB0aGVzZSBmdW5jdGlvbnMgaXMgY3J1Y2lhbCBmb3Igd3JpdGluZyBlZmZpY2llbnQgUiBjb2RlLCBlc3BlY2lhbGx5IHdoZW4gZGVhbGluZyB3aXRoIGxhcmdlIGRhdGFzZXRzIG9yIGNvbXBsZXggY29tcHV0YXRpb25zLgoKRXZlbiB3aGVuIHRoZSB1c2Ugb2YgdGhlIGBhcHBseSgpYCBmdW5jdGlvbnMgcmVzdWx0cyBpbiBiZXR0ZXIgcGVyZm9ybWFuY2UsIHNvbWUgcHJvZ3JhbW1lcnMgbWlnaHQgZmluZCBsb29wcyBtb3JlIGludHVpdGl2ZSBlc3BlY2lhbGx5IHdoZW4gY29taW5nIGZyb20gYSBwcm9jZWR1cmFsIGxhbmd1YWdlIHN1Y2ggYXMgQysrLiBUaGVyZWZvcmUsIGEgZmlyc3QgaW1wbGVtZW50YXRpb24gb2YgYW4gYWxnb3JpdGhtIG1pZ2h0IHVzZSBsb29wcy4gT25seSBvbmNlIHRoZSBjb2RlIGlzIHJ1bm5pbmcgY29ycmVjdGx5LCBkbyBzb21lIHByb2dyYW1tZXJzIHRyYW5zaXRpb24gdG8gdGhlIHVzZSBvZiB0aGUgYGFwcGx5KClgIGZ1bmN0aW9ucy4gT2YgY291cnNlLCBhcyBvbmUgYmVjb21lcyBtb3JlIGZhbWlsaWFyIHdpdGggUiwgY29kZSBmb2xsb3dzIG1vcmUgb2YgdGhlIG5hdHVyYWwgUiBwcm9ncmFtbWluZyBpZGlvbXMuCgojIyMgMi4gVXNlIGB3aGljaCgpYAoKUmF0aGVyIHRoYW4gbG9vcGluZyB0aHJvdWdoIGEgdmVjdG9yIG9yIGEgY29sdW1uIGluIGEgZGF0YSBmcmFtZSwgdXNlIHRoZSBgd2hpY2goKWAgZnVuY3Rpb24gKGFuZCBpdHMgZXhpc3RlbnRpYWwgY291bnRlcnBhcnQgYGFueSgpYCkgYXMgaXQgaXMgbXVjaCBmYXN0ZXIuIFRoZSBjb2RlIGJlbG93IGRlbW9uc3RyYXRlcyB0aGlzIHdoZW4gc2VhcmNoaW5nIGEgdmVjdG9yIGZvciB0aGUgcG9zaXRpb24gb2YgYSBwYXJ0aWN1bGFyIHZhbHVlIChmaW5kcyB0aGUgZmlyc3Qgb2NjdXJyZW5jZSBvbmx5KToKCmBgYHtyIHVzZVdoaWNofQpuIDwtIDFlOCAgICAgICMgc2l6ZSBvZiB2ZWN0b3IKCiMgdmVjdG9yIG9mIHJhbmRvbSBpbnRlZ2VyIHZhbHVlcwp2IDwtIHJvdW5kKHJ1bmlmKG4sIG1pbiA9IDEwMCwgbWF4ID0gbipuKSwwKQoKeCA8LSA0NDU4NzYgICAjIHZhbHVlIHRvIGZpbmQKayA8LSAwICAgICAgICAjIHBvc2l0aW9uIGF0IHdoaWNoIGZvdW5kCgojIGluc2VydCB2YWx1ZSBhdCBhIGxhc3QgcG9zaXRpb24gdG8gZW5zdXJlIGl0IGlzIHByZXNlbnQKdltuXSA8LSB4CmBgYAoKTm93LCBsZXQncyB0cnkgdG8gZmluZCB0aGUgcG9zaXRpb24gb2YgdGhlIGtleSB2YWx1ZSAqeCogaW4gdGhlIHZlY3RvciBgdmAuIFdlIHdpbGwgbWVhc3VyZSB0aGUgcnVuLXRpbWUgcGVyZm9ybWFuY2Ugb2YgYm90aCBhcHByb2FjaGVzIChvZiBjb3Vyc2UsIG9uIHlvdXIgY29tcHV0ZXIgdGhlIHJhbmRvbSB2YWx1ZXMgaW4gYHZgIGFuZCB0aGUgdGltaW5ncyB3aWxsIGJlIGRpZmZlcmVudCkuCgoqKkFwcHJvYWNoIEk6IExpbmVhciBTZWFyY2ggd2l0aCBMb29wcyoqCgpgYGB7cn0KYnQgPC0gU3lzLnRpbWUoKQoKZm9yIChpIGluIDE6bikgewogIGlmICh4ID09IHZbaV0pIHsKICAgIGsgPC0gaQogICAgYnJlYWsKICB9Cn0KCmV0IDwtIFN5cy50aW1lKCkKCnQuSSA8LSBldCAtIGJ0CgpjYXQoIkFwcHJvYWNoIEkgLyBMb29wOiBmb3VuZCAiLCB4LCAiYXQgcG9zaXRpb24iLCBrLCAiaW4iLCByb3VuZCgodC5JKSwzKSwgInNlY29uZHMiKQpgYGAKCioqQXBwcm9hY2ggSUk6IFVzaW5nIGB3aGljaCgpYCoqCgpUaGUgYXBwcm9hY2ggYmVsb3cgdXNlcyB0aGUgYHdoaWNoKClgIGZ1bmN0aW9uOyBhcyB5b3UgY2FuIHNlZSBpdCBpcyBzdWJzdGFudGlhbGx5IGZhc3RlciB0aGFuIGxvb3BpbmcuCgpgYGB7cn0KYnQgPC0gU3lzLnRpbWUoKQoKayA8LSB3aGljaCh4ID09IHYpCgpldCA8LSBTeXMudGltZSgpCgp0LklJIDwtIGV0IC0gYnQKCmNhdCgiQXBwcm9hY2ggSUkgLyB3aGljaDogZm91bmQgIiwgeCwgImF0IHBvc2l0aW9uIiwgaywgImluIiwgcm91bmQoKHQuSUkpLDMpLCAic2Vjb25kcyIpCmBgYAoKVGhlIGRpZmZlcmVuY2UgaW4gdGltZSBpcyBxdWl0ZSBwcm9ub3VuY2VkIC0tIGFib3V0IGEgMTB4IGltcHJvdmVtZW50IGluIHNwZWVkLgoKT2YgY291cnNlLCBpZiB0aGUgdmFsdWVzIGluIHRoZSB2ZWN0b3IgaGFkIGJlZW4gc29ydGVkLCB0aGVuIGEgYmluYXJ5IHNlYXJjaCB3b3VsZCBoYXZlIGJlZW4gc3Vic3RhbnRpYWxseSBmYXN0ZXIgKGNvbXBsZXhpdHkgb2YgJE8obG9nX24pJCB2cyAkTyhuKSQpLiBBbmQsIHBsYWNpbmcgdGhlIHZhbHVlcyBpbnRvIGEgaGFzaG1hcCByYXRoZXIgdGhhbiBhIGxpbmVhciB2ZWN0b3Igd291bGQgYWxzbyBtYWtlIHNlYXJjaCBmYXN0ZXIgKCRPKDEpJCkgLS0gaG93ZXZlciwgUiBkb2VzIG5vdCBoYXZlIGJ1aWx0LWluIHN1cHBvcnQgZm9yIGhhc2htYXBzLCBzbyBtZWNoYW5pc21zIHN1Y2ggYXMgYW4gaW4tbWVtb3J5IGtleS12YWx1ZSBkYXRhYmFzZSAoKmUuZy4qLCAqbWVtY2FjaGVkKikgYXJlIG9mdGVuIHVzZWQuCgojIyMjIFF1aWNrIFR1dG9yaWFsOiBgd2hpY2goKWAKClRoZSBgd2hpY2goKWAgZnVuY3Rpb24gaW4gUiBpcyBhbiBlZmZpY2llbnQgbWVjaGFuaXNtIGZvciBpZGVudGlmeWluZyB0aGUgaW5kaWNlcyBvZiBlbGVtZW50cyBpbiBhIGxvZ2ljYWwgdmVjdG9yIHRoYXQgbWVldCBhIHNwZWNpZmllZCBjb25kaXRpb24uIEl0IGlzIG9mdGVuIHVzZWQgYXMgYW4gYWx0ZXJuYXRpdmUgdG8gbG9vcHMgZm9yIGNvbmRpdGlvbmFsIHNlYXJjaGVzLCBwcm92aWRpbmcgYSBtb3JlIGNvbmNpc2UgYW5kIHR5cGljYWxseSBmYXN0ZXIgd2F5IHRvIGFjY29tcGxpc2ggc3VjaCB0YXNrcy4gUmVjYWxsIHRoYXQgYSBjb2x1bW4gaW4gYSBkYXRhIGZyYW1lIGlzIGEgdmVjdG9yLCBzbyB0aGlzIGFsc28gY2FuIGJlIHVzZWQgdG8gc2VhcmNoIGNvbHVtbnMgb2YgZGF0YSBmcmFtZXMuCgpUaGUgYHdoaWNoKClgIGZ1bmN0aW9uIHJldHVybnMgdGhlIHBvc2l0aW9ucyBpbiBhIHZlY3RvciB3aGVyZSBhbiBlbGVtZW50IGluIHRoZSB2ZWN0b3IgbWVldHMgYSBsb2dpY2FsIGNvbmRpdGlvbi4gRXNzZW50aWFsbHksIGl0IHNjYW5zIHRocm91Z2ggYSBsb2dpY2FsIHZlY3RvciBhbmQgaWRlbnRpZmllcyB0aGUgcG9zaXRpb25zIHdoZXJlIHRoZSBjb25kaXRpb24gaXMgbWV0LgoKQ29uc2lkZXIgYSBzaW1wbGUgZXhhbXBsZSB3aGVyZSB3ZSB3YW50IHRvIGZpbmQgdGhlIHBvc2l0aW9ucyAoaW5kaWNlcykgb2YgZWxlbWVudHMgaW4gYSBudW1lcmljIHZlY3RvciB0aGF0IGFyZSBncmVhdGVyIHRoYW4gYSBzcGVjaWZpZWQgdmFsdWUuIEluIHRoaXMgZXhhbXBsZSwgYHdoaWNoKHZlYyA+IDUpYCByZXR1cm5zIHRoZSBpbmRpY2VzIG9mIGB2ZWNgIHdoZXJlIHRoZSBlbGVtZW50cyBhcmUgZ3JlYXRlciB0aGFuIDUuCgpgYGB7cn0KIyBDcmVhdGUgYSBudW1lcmljIHZlY3Rvcgp2ZWMgPC0gYygyLCA0LCA2LCA4LCAxMCwgMywgNSwgNywgOSkKCiMgVXNlIHdoaWNoKCkgdG8gZmluZCBwb3NpdGlvbnMgb2YgZWxlbWVudHMgZ3JlYXRlciB0aGFuIDUKaW5kaWNlcyA8LSB3aGljaCh2ZWMgPiA1KQoKcHJpbnQoaW5kaWNlcykKYGBgCgpUaGUgYHdoaWNoKClgIGZ1bmN0aW9uIGlzIGFsc28gdXNlZnVsIGZvciBpZGVudGlmeWluZyByb3dzIGluIGEgZGF0YSBmcmFtZSB0aGF0IG1lZXQgY2VydGFpbiBjb25kaXRpb25zLiBMZXQncyBjb25zaWRlciBhIGRhdGEgZnJhbWUgZXhhbXBsZToKCmBgYHtyfQojIENyZWF0ZSBhIGRhdGEgZnJhbWUKZGYgPC0gZGF0YS5mcmFtZSgKICBJRCA9IDE6MTAsCiAgU2NvcmUgPSBjKDg1LCA5MCwgODgsIDc4LCA5MiwgOTUsIDcwLCA2NSwgODgsIDkxKQopCgojIHNlIHdoaWNoKCkgdG8gZmluZCByb3dzIHdoZXJlIFNjb3JlIGlzIGdyZWF0ZXIgdGhhbiA5MApyb3dzIDwtIHdoaWNoKGRmJFNjb3JlID4gOTApCgpwcmludChyb3dzKQpgYGAKCk9mdGVuLCB5b3Ugd2FudCB0byBzdWJzZXQgdGhlIG9yaWdpbmFsIHZlY3RvciBvciBkYXRhIGZyYW1lIGJhc2VkIG9uIHRoZSBpbmRpY2VzIHJldHVybmVkIGJ5IGB3aGljaCgpYC4gSGVyZSdzIGhvdyB5b3UgY2FuIGRvIGl0OgoKYGBge3J9CiMgc2VsZWN0IHJvd3MgaW4gdGhlIGRhdGEgZnJhbWUgYmFzZWQgb24gY29uZGl0aW9uIGluIGEgY29sdW1uCmRmLnN1YnNldCA8LSBkZlt3aGljaChkZiRTY29yZSA+IDkwKSwgXQoKaGVhZChkZi5zdWJzZXQpCmBgYAoKVGhlIGB3aGljaCgpYCBmdW5jdGlvbiBpcyBtb3JlIGVmZmljaWVudCB0aGFuIGxvb3BzIGZvciBpZGVudGlmeWluZyBpbmRpY2VzIHRoYXQgbWVldCBhIGNvbmRpdGlvbiwgYXMgaXQgbGV2ZXJhZ2VzIGludGVybmFsIG9wdGltaXphdGlvbnMuIFVzaW5nIGB3aGljaCgpYCBtYWtlcyB0aGUgY29kZSBtb3JlIGNvbmNpc2UgYW5kIHJlYWRhYmxlIGNvbXBhcmVkIHRvIHdyaXRpbmcgZXhwbGljaXQgbG9vcHMgLS0gaWYgb25lIGlzIHVzZWQgdG8gUi4gSG93ZXZlciwgaXQgaXMgdGhlIG5hdHVyYWwgYW5kIGlkaW9tYXRpYyB3YXkgdG8gcHJvZ3JhbSBpbiBSLgoKIyMjIDMuIFVzZSBJbnRlZ2VyIEtleXMKCktleXMgc2hvdWxkIGJlIGludGVnZXJzIHdoZW5ldmVyIHBvc3NpYmxlIHJhdGhlciB0aGFuIGNoYXJhY3RlciBzdHJpbmdzIGFzIGNvbXBhcmluZyBpbnRlZ2VycyBpcyBtdWNoIGZhc3RlciB0aGFuIGNvbXBhcmluZyB0ZXh0IHN0cmluZ3MgKHdoaWNoIGFyZSBzZXF1ZW5jZXMgb2YgY2hhcmFjdGVycyB0aGF0IGhhdmUgdG8gYmUgY29tcGFyZWQgb25lIGNoYXJhY3RlciBhdCBhIHRpbWUpLiBPZiBjb3Vyc2UsIHVzaW5nIGEgaGFzaCBmdW5jdGlvbiB0byBtYXAgc3RyaW5ncyB0byBpbnRlZ2VycyB3b3VsZCBiZSBhIGdvb2QgYWx0ZXJuYXRpdmUuIFRoZSBjb2RlIGJlbG93IGNvbXBhcmVzIHRoZSB0aW1lIHRvIHNlYXJjaCBhbiBpbnRlZ2VyIGNvbHVtbiB2ZXJzdXMgYSB0ZXh0IGNvbHVtbi4KCmBgYHtyfQpuIDwtIDFlNwoKZGYgPC0gZGF0YS5mcmFtZSgKICBJRCA9IHJvdW5kKHJ1bmlmKG4sIG1pbiA9IDEwMDAsIG1heCA9IDEwMDAwMCksMCksCiAgU2NvcmUgPSByb3VuZChydW5pZihuLCBtaW4gPSA0MCwgbWF4ID0gOTkpLDApCikKCiMgZW1iZWQgbG9va3VwIHZhbHVlIGluIHRoZSBsYXN0IHJvdwpsb29rdXAudmFsdWUuaW50IDwtIDQ0NTYzMgpkZiRJRFtucm93KGRmKV0gPC0gbG9va3VwLnZhbHVlLmludAoKIyBhZGQgYSB0ZXh0IGNvbHVtbgpkZiROVUlEIDwtIGFzLmNoYXJhY3RlcihkZiRJRCkKbG9va3VwLnZhbHVlLmNociA8LSBhcy5jaGFyYWN0ZXIobG9va3VwLnZhbHVlLmludCkKZGYkTlVJRFtucm93KGRmKV0gPC0gbG9va3VwLnZhbHVlLmNocgpgYGAKCioqSW50ZWdlciBLZXkgU2VhcmNoOioqCgpgYGB7cn0KYnQgPC0gU3lzLnRpbWUoKQoKIyBsb29rdXAgc2NvcmUgYmFzZWQgb24gSUQKayA8LSBkZiRTY29yZVt3aGljaChkZiRJRCA9PSBsb29rdXAudmFsdWUuaW50KV0KCmV0IDwtIFN5cy50aW1lKCkKCnQuaW50ZWdlciA8LSBldCAtIGJ0CgpjYXQoIkludGVnZXIgS2V5OiIsIHJvdW5kKCh0LmludGVnZXIpLDMpLCAic2Vjb25kcyIpCmBgYAoKKipUZXh0L0NoYXJhY3RlciBLZXkgU2VhcmNoOioqCgpgYGB7cn0KYnQgPC0gU3lzLnRpbWUoKQoKIyBsb29rdXAgc2NvcmUgYmFzZWQgb24gSUQKayA8LSBkZiRTY29yZVt3aGljaChkZiROVUlEID09IGxvb2t1cC52YWx1ZS5jaHIpXQoKZXQgPC0gU3lzLnRpbWUoKQoKdC50ZXh0IDwtIGV0IC0gYnQKCmNhdCgiVGV4dCBLZXk6Iiwgcm91bmQoKHQudGV4dCksMyksICJzZWNvbmRzIikKYGBgCgpUaGUgbG9va3VwIG9mIGEgY2hhcmFjdGVyIGtleSBpcyAxMHggc2xvd2VyLiBBbHRob3VnaCwgdG8gYmUgZmFpciwgaXQgaXMgcXVpdGUgZmFzdCB3aGVuIHVzaW5nIGB3aGljaCgpYC4gVHJ5IHdyaXRpbmcgdGhlIHNhbWUgY29kZSB3aXRoIGEgbG9vcCBmb3IgY29tcGFyaXNvbi4gV2hhdCBkbyB5b3Ugbm90aWNlPyBXaGF0IGlzIHRoZSBwZXJmb3JtYW5jZSBkaWZmZXJlbmNlPwoKIyMjIDQuIExldmVyYWdlIEVmZmljaWVudCBEYXRhIE1hbmlwdWxhdGlvbiBQYWNrYWdlcwoKT25lIG9mIHRoZSBwcmltYXJ5IHdheXMgdG8gZW5oYW5jZSBwZXJmb3JtYW5jZSBpcyB0aHJvdWdoIGVmZmljaWVudCBkYXRhIG1hbmlwdWxhdGlvbi4gRGF0YSBmcmFtZXMgaW4gUiBhcmUgdmVyc2F0aWxlLCBidXQgdGhleSBtYXkgbm90IGFsd2F5cyBiZSB0aGUgYmVzdCBjaG9pY2UgZm9yIHBlcmZvcm1hbmNlLWNyaXRpY2FsIGFwcGxpY2F0aW9ucy4gSW5zdGVhZCwgY29uc2lkZXIgdXNpbmcgdGhlIGBkYXRhLnRhYmxlYCBwYWNrYWdlLCB3aGljaCBvZmZlcnMgYW4gZW5oYW5jZWQgdmVyc2lvbiBvZiBkYXRhIGZyYW1lcy4gRGF0YSB0YWJsZXMgYXJlIGRlc2lnbmVkIGZvciBmYXN0IGFnZ3JlZ2F0aW9uLCBqb2luaW5nLCBhbmQgaW4tcGxhY2UgdXBkYXRlcy4gVGhleSBhbHNvIGNvbnN1bWUgbGVzcyBtZW1vcnkgYW5kIGV4ZWN1dGUgb3BlcmF0aW9ucyBtb3JlIHF1aWNrbHkgZHVlIHRvIHRoZWlyIG9wdGltaXplZCBpbnRlcm5hbCBzdHJ1Y3R1cmUuCgpGb3IgZXhhbXBsZSwgc3VwcG9zZSB5b3UgaGF2ZSBhIGxhcmdlIGRhdGFzZXQgYW5kIG5lZWQgdG8gcGVyZm9ybSBmcmVxdWVudCBzdWJzZXR0aW5nIGFuZCBhZ2dyZWdhdGlvbnMuIFVzaW5nIGBkYXRhLnRhYmxlYCBjYW4gc2lnbmlmaWNhbnRseSByZWR1Y2UgZXhlY3V0aW9uIHRpbWUuIEhlcmUgaXMgYSBkZW1vbnN0cmF0aW9uOgoKKipVc2luZyBhIERhdGEgRnJhbWU6KioKCmBgYHtyfQojIENyZWF0aW5nIGEgbGFyZ2UgZGF0YSBmcmFtZQpkZiA8LSBkYXRhLmZyYW1lKHggPSBybm9ybSgxZTgpLCAKICAgICAgICAgICAgICAgICB5ID0gcm5vcm0oMWU4KSkKCiMgU3Vic2V0dGluZyBhbmQgYWdncmVnYXRpb24Kc3lzdGVtLnRpbWUoewogIHJlc3VsdCA8LSBtZWFuKGRmJHlbd2hpY2goZGYkeCA+IDApXSkKfSkKYGBgCgoqKlVzaW5nIGEgYGRhdGEudGFibGVgOioqCgpgYGB7ciBlY2hvID0gRiwgd2FybmluZz1GLCBtZXNzYWdlPUZ9CnBhY2thZ2UgPC0gImRhdGEudGFibGUiCgppZiAoIXJlcXVpcmUocGFja2FnZSwgY2hhcmFjdGVyLm9ubHkgPSBUUlVFKSkgewogIGluc3RhbGwucGFja2FnZXMocGFja2FnZSwgZGVwZW5kZW5jaWVzID0gVFJVRSwgcXVpZXRseSA9IFRSVUUpCn0KCmxpYnJhcnkocGFja2FnZSwgY2hhcmFjdGVyLm9ubHkgPSBUUlVFKQpgYGAKCmBgYHtyIG1lc3NhZ2U9Rn0KbGlicmFyeShkYXRhLnRhYmxlKQoKIyBDcmVhdGluZyBhIGxhcmdlIGRhdGEgdGFibGUKZHQgPC0gZGF0YS50YWJsZSh4ID0gcm5vcm0oMWU4KSwgCiAgICAgICAgICAgICAgICAgeSA9IHJub3JtKDFlOCkpCgojIFN1YnNldHRpbmcgYW5kIGFnZ3JlZ2F0aW9uCnN5c3RlbS50aW1lKHsKICByZXN1bHQgPC0gZHRbeCA+IDAsIC4obWVhbl95ID0gbWVhbih5KSldCn0pCmBgYAoKSW4gdGhpcyBleGFtcGxlLCBgZGF0YS50YWJsZWAgcHJvY2Vzc2VzIHRoZSBzdWJzZXR0aW5nIGFuZCBhZ2dyZWdhdGlvbiBhIGJpdCBmYXN0ZXIgdGhhbiBhIHJlZ3VsYXIgZGF0YSBmcmFtZSwgbWFraW5nIGl0IGlkZWFsIGZvciBsYXJnZS1zY2FsZSBkYXRhIGFuYWx5c2lzLCBwYXJ0aWN1bGFybHkgd2hlbiB0aGVyZSBhcmUgbWFueSBjb2x1bW5zLgoKIyMjIDUuIFZlY3Rvcml6ZSBPcGVyYXRpb25zCgpWZWN0b3JpemF0aW9uIGlzIGFub3RoZXIgY3JpdGljYWwgdGVjaG5pcXVlIGZvciBpbXByb3ZpbmcgcGVyZm9ybWFuY2UuIFIgaXMgaW5oZXJlbnRseSBhIHZlY3Rvcml6ZWQgbGFuZ3VhZ2UsIG1lYW5pbmcgaXQgY2FuIG9wZXJhdGUgb24gZW50aXJlIHZlY3RvcnMgb2YgZGF0YSBhdCBvbmNlLiBCeSBsZXZlcmFnaW5nIHZlY3Rvcml6ZWQgb3BlcmF0aW9ucywgeW91IGNhbiBhdm9pZCB0aGUgb3ZlcmhlYWQgb2YgZXhwbGljaXQgbG9vcHMsIHdoaWNoIGFyZSBvZnRlbiBzbG93IGluIFIuIEZvciBpbnN0YW5jZSwgaW5zdGVhZCBvZiB1c2luZyBhIGxvb3AgdG8gYWRkIHR3byB2ZWN0b3JzIGVsZW1lbnQtd2lzZSwgeW91IGNhbiBkaXJlY3RseSB1c2UgdmVjdG9yaXplZCBhZGRpdGlvbjoKCmBgYHtyfQojIFZlY3Rvcml6ZWQgYWRkaXRpb24KYSA8LSBybm9ybSgxZTcpCmIgPC0gcm5vcm0oMWU3KQoKc3lzdGVtLnRpbWUoewogIGMgPC0gc3VtKGEgKyBiKQp9KQpgYGAKCkhlcmUsIHRoZSB2ZWN0b3JpemVkIGFkZGl0aW9uIGlzIG5vdCBvbmx5IG1vcmUgY29uY2lzZSBidXQgYWxzbyBtdWNoIGZhc3RlciB0aGFuIGxvb3BpbmcgdGhyb3VnaCBlYWNoIGVsZW1lbnQgYXMgZGVtb25zdHJhdGVkIHdpdGggdGhlIGxvb3AtYmFzZWQgY29kZSBiZWxvdzoKCmBgYHtyfQojIFZlY3Rvcml6ZWQgYWRkaXRpb24KYSA8LSBybm9ybSgxZTcpCmIgPC0gcm5vcm0oMWU3KQpjIDwtIDAKCnN5c3RlbS50aW1lKHsKICBmb3IgKGkgaW4gMTpsZW5ndGgoYSkpIHsKICAgIGMgPC0gYyArIChhW2ldICsgYltpXSkKICB9Cn0pCmBgYAoKIyMjIDYuIFByZWFsbG9jYXRlIE1lbW9yeQoKTWVtb3J5IG1hbmFnZW1lbnQgaXMgYW5vdGhlciBhc3BlY3Qgd2hlcmUgcGVyZm9ybWFuY2UgY2FuIGJlIGltcHJvdmVkLiBSJ3MgZ2FyYmFnZSBjb2xsZWN0b3IgaGFuZGxlcyBtZW1vcnkgYWxsb2NhdGlvbiBhbmQgZGVhbGxvY2F0aW9uIGF1dG9tYXRpY2FsbHksIGJ1dCBpbmVmZmljaWVudCBtZW1vcnkgdXNhZ2UgY2FuIHN0aWxsIHNsb3cgZG93biB5b3VyIGNvZGUuIFByZS1hbGxvY2F0aW5nIG1lbW9yeSBmb3IgbGFyZ2Ugb2JqZWN0cyBjYW4gcHJldmVudCB1bm5lY2Vzc2FyeSBtZW1vcnkgcmVhbGxvY2F0aW9uIGR1cmluZyBleGVjdXRpb24uIEZvciBleGFtcGxlLCBpZiB5b3UgYXJlIGFwcGVuZGluZyBlbGVtZW50cyB0byBhIHZlY3RvciBpbnNpZGUgYSBsb29wLCBpdCBpcyBiZXR0ZXIgdG8gcHJlLWFsbG9jYXRlIHRoZSB2ZWN0b3IncyBzaXplIHRoYW4gZ3Jvd2luZyB0aGUgdmVjdG9yIGR5bmFtaWNhbGx5IGFzIG5ldyBlbGVtZW50cyBhcmUgaW5zZXJ0ZWQuCgpJbiB0aGUgY29kZSBiZWxvdywgdGhlIGluaXRpYWwgdmVjdG9yIGlzIGNyZWF0ZWQgZW1wdHk7IGFzIG5ldyBlbGVtZW50cyBhcmUgaW5zZXJ0ZWQsIFIgYXV0b21hdGljYWxseSBhbGxvY2F0ZXMgbWVtb3J5LiBHZW5lcmFsbHksIHRoaXMgbWVhbnMgdGhhdCBtZW1vcnkgZm9yIGEgbmV3IHZlY3RvciB3aXRoIGEgc2l6ZSBvbmUgZWxlbWVudCBsYXJnZXIgdGhhbiB0aGUgb3JpZ2luYWwgdmVjdG9yIGlzIGFsbG9jYXRlZCBhbmQgdGhlbiB0aGUgb3JpZ2luYWwgdmVjdG9yJ3MgZWxlbWVudHMgYXJlIGNvcGllZCB0byB0aGUgbmV3IHZlY3Rvci4KCmBgYHtyfQojIGR5bmFtaWNhbGx5IGdyb3dpbmcgYSB2ZWN0b3IKbiA8LSAxZTcKdiA8LSBudW1lcmljKDApCgpzeXN0ZW0udGltZSh7CiAgZm9yIChpIGluIDE6bikgewogICAgdltpXSA8LSBybm9ybSgxKQogIH0KfSkKYGBgCgpUaGUgY29kZSBiZWxvdyBwcmUtYWxsb2NhdGVzIHRoZSBtZW1vcnkuIE9mIGNvdXJzZSwgdGhpcyBvbmx5IHdvcmtzIHdoZW4gdGhlIHJlcXVpcmVkIG51bWJlciBvZiBlbGVtZW50cyBpcyBrbm93biBiZWZvcmVoYW5kLiBJZiBpdCBpcyBub3Qga25vd24sIHRoZW4gdGhlIG1lbW9yeSBtdXN0IGJlIGVzdGltYXRlZCwgbWFraW5nIGNlcnRhaW4gbm90IHRvIG92ZXJhbGxvY2F0ZS4KCmBgYHtyfQojIHByZS1hbGxvY2F0aW5nIG1lbW9yeSBmb3IgYSB2ZWN0b3IKbiA8LSAxZTcKdiA8LSBudW1lcmljKG4pCgpzeXN0ZW0udGltZSh7CiAgZm9yIChpIGluIDE6bikgewogICAgdltpXSA8LSBybm9ybSgxKQogIH0KfSkKYGBgCgpUaGlzIGFwcHJvYWNoIGF2b2lkcyB0aGUgb3ZlcmhlYWQgYXNzb2NpYXRlZCB3aXRoIGR5bmFtaWNhbGx5IGdyb3dpbmcgdGhlIHZlY3Rvci4gVGhlIGVmZmVjdCBiZWNvbWVzIG1vcmUgcHJvbm91bmNlZCBvdmVyIHRpbWUuCgojIyMgNy4gUGFyYWxsZWxpemUgUHJvY2Vzc2luZwoKUGFyYWxsZWwgY29tcHV0aW5nIGNhbiBhbHNvIHNpZ25pZmljYW50bHkgcmVkdWNlIGNvbXB1dGF0aW9uIHRpbWUgZm9yIHRhc2tzIHRoYXQgY2FuIGJlIHBhcmFsbGVsaXplZC4gUiBvZmZlcnMgc2V2ZXJhbCBwYWNrYWdlcyBmb3IgcGFyYWxsZWwgcHJvY2Vzc2luZywgc3VjaCBhcyBgcGFyYWxsZWxgLCBgZm9yZWFjaGAsIGFuZCBgZnV0dXJlYC4gVGhlIGBwYXJhbGxlbGAgcGFja2FnZSwgZm9yIGluc3RhbmNlLCBwcm92aWRlcyBmdW5jdGlvbnMgdG8gZXhlY3V0ZSBjb2RlIG9uIG11bHRpcGxlIENQVSBjb3JlcyBzaW11bHRhbmVvdXNseS4gT2YgY291cnNlLCB0aGUgbW9yZSBjb3JlcyBhIENQVSBoYXMsIHRoZSBiZXR0ZXIuCgpIZXJl4oCZcyBhbiBleGFtcGxlIHVzaW5nIHRoZSBgbWNsYXBwbHlgIGZ1bmN0aW9uOgoKYGBge3IgZWNobyA9IEYsIHdhcm5pbmc9RiwgbWVzc2FnZT1GfQpwYWNrYWdlIDwtICJwYXJhbGxlbCIKCmlmICghcmVxdWlyZShwYWNrYWdlLCBjaGFyYWN0ZXIub25seSA9IFRSVUUpKSB7CiAgaW5zdGFsbC5wYWNrYWdlcyhwYWNrYWdlLCBkZXBlbmRlbmNpZXMgPSBUUlVFLCBxdWlldGx5ID0gVFJVRSkKfQoKbGlicmFyeShwYWNrYWdlLCBjaGFyYWN0ZXIub25seSA9IFRSVUUpCmBgYAoKYGBge3J9CmxpYnJhcnkocGFyYWxsZWwpCgojIFBhcmFsbGVsIHByb2Nlc3NpbmcgdXNpbmcgbWNsYXBwbHkKc3lzdGVtLnRpbWUoewogIHJlc3VsdCA8LSBtY2xhcHBseSgxOjgsIGZ1bmN0aW9uKHgpIHsKICAgIHN1bShybm9ybSgxZTYpKQogIH0sIG1jLmNvcmVzID0gNCkKfSkKYGBgCgpJbiB0aGlzIGV4YW1wbGUsIHRoZSBjb21wdXRhdGlvbiBpcyBkaXN0cmlidXRlZCBhY3Jvc3MgZm91ciBjb3JlcywgcmVzdWx0aW5nIGluIGEgc3Vic3RhbnRpYWwgZGVjcmVhc2UgaW4gZXhlY3V0aW9uIHRpbWUgY29tcGFyZWQgdG8gYSBzaW5nbGUtdGhyZWFkZWQgYXBwcm9hY2guCgojIyMgOC4gUHJvZmlsZSBDb2RlCgpQcm9maWxpbmcgeW91ciBjb2RlIGlzIGFuIGVzc2VudGlhbCBzdGVwIGluIGlkZW50aWZ5aW5nIHBlcmZvcm1hbmNlIGJvdHRsZW5lY2tzLiBUaGUgYHByb2Z2aXNgIHBhY2thZ2UgaW4gUiBwcm92aWRlcyBhIGdyYXBoaWNhbCBpbnRlcmZhY2UgZm9yIHByb2ZpbGluZywgYWxsb3dpbmcgeW91IHRvIHZpc3VhbGl6ZSB3aGVyZSB5b3VyIGNvZGUgc3BlbmRzIHRoZSBtb3N0IHRpbWUuIEJ5IHBpbnBvaW50aW5nIHRoZXNlIGhvdHNwb3RzLCB5b3UgY2FuIGZvY3VzIHlvdXIgb3B0aW1pemF0aW9uIGVmZm9ydHMgbW9yZSBlZmZlY3RpdmVseS4KCmBgYHtyIGVjaG8gPSBGLCB3YXJuaW5nPUYsIG1lc3NhZ2U9Rn0KcGFja2FnZSA8LSAicHJvZnZpcyIKCmlmICghcmVxdWlyZShwYWNrYWdlLCBjaGFyYWN0ZXIub25seSA9IFRSVUUpKSB7CiAgaW5zdGFsbC5wYWNrYWdlcyhwYWNrYWdlLCBkZXBlbmRlbmNpZXMgPSBUUlVFLCBxdWlldGx5ID0gVFJVRSkKfQoKbGlicmFyeShwYWNrYWdlLCBjaGFyYWN0ZXIub25seSA9IFRSVUUpCmBgYAoKYGBge3J9CmxpYnJhcnkocHJvZnZpcykKCiMgUHJvZmlsaW5nIGNvZGUgZXhlY3V0aW9uCnByb2Z2aXMoewogIHJlc3VsdCA8LSBzYXBwbHkoMToxZTYsIGZ1bmN0aW9uKHgpIHheMikKfSkKYGBgCgpUaGlzIHByb2ZpbGluZyB0b29sIGhlbHBzIHlvdSB1bmRlcnN0YW5kIHRoZSB0aW1lIGNvbXBsZXhpdHkgb2YgZGlmZmVyZW50IGNvZGUgc2VjdGlvbnMsIGd1aWRpbmcgeW91IHRvd2FyZHMgdGFyZ2V0ZWQgaW1wcm92ZW1lbnRzLgoKIyMjIDguIExldmVyYWdlIEdlbkFJCgpHZW5lcmF0aXZlIEFJIGFzc2lzdGFudHMsIHN1Y2ggYXMgQ2hhdEdQVCwgQ28tUGlsb3QsIGFuZCBDbGF1ZGUsIGNhbiBiZSBxdWl0ZSB2YWx1YWJsZSBpbiBpZGVudGlmeWluZyBhbmQgcmVzb2x2aW5nIHBlcmZvcm1hbmNlIGlzc3VlcyBpbiBSIGNvZGUuIFRoZXNlIEFJIHN5c3RlbXMgY2FuIGFzc2lzdCBib3RoIG5vdmljZSBhbmQgZXhwZXJpZW5jZWQgcHJvZ3JhbW1lcnMgYnkgcHJvdmlkaW5nIGluc2lnaHRzLCBjb2RlIHJldmlld3MsIG9wdGltaXphdGlvbiBzdWdnZXN0aW9ucywgYW5kIGVkdWNhdGlvbmFsIHJlc291cmNlcy4gTGV0J3MgZXhwbG9yZSBzb21lIHdheXMgdGhlc2UgQUkgYXNzaXN0YW50cyBjYW4gYmUgbGV2ZXJhZ2VkIHRvIGltcHJvdmUgdGhlIHBlcmZvcm1hbmNlIG9mIFIgY29kZS4KCk9uZSBvZiB0aGUgcHJpbWFyeSB3YXlzIGdlbmVyYXRpdmUgQUkgYXNzaXN0YW50cyBjYW4gaGVscCBpcyBieSByZXZpZXdpbmcgeW91ciBSIGNvZGUgYW5kIHN1Z2dlc3Rpbmcgb3B0aW1pemF0aW9ucy4gWW91IGNhbiBpbnB1dCBzZWN0aW9ucyBvZiB5b3VyIGNvZGUgYW5kIGFzayB0aGUgQUkgdG8gYW5hbHl6ZSBpdCBmb3IgcG90ZW50aWFsIHBlcmZvcm1hbmNlIGJvdHRsZW5lY2tzLiBGb3IgZXhhbXBsZSwgaWYgeW91IGhhdmUgYSBwaWVjZSBvZiBjb2RlIHRoYXQgaW52b2x2ZXMgbG9vcHMgb3IgaW5lZmZpY2llbnQgZGF0YSBtYW5pcHVsYXRpb25zLCB0aGUgQUkgY2FuIHN1Z2dlc3QgbW9yZSBlZmZpY2llbnQgYWx0ZXJuYXRpdmVzLCBzdWNoIGFzIHZlY3Rvcml6ZWQgb3BlcmF0aW9ucyBvciB0aGUgdXNlIG9mIHRoZSBgZGF0YS50YWJsZWAgcGFja2FnZS4KCkNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgZXhhbXBsZSB3aGVyZSBhbiBBSSBhc3Npc3RhbnQgaXMgYXNrZWQgdG8gb3B0aW1pemUgYSBsb29wIHdpdGggdGhlIGZvbGxvd2luZyBwcm9tcHQgZm9sbG93ZWQgYnkgcGFzdGluZyB0aGUgY29kZToKCmBgYCAgICAgICAgIApPcHRpbWl6ZSB0aGUgZm9sbG93aW5nIFIgY29kZSBmb3IgcGVyZm9ybWFuY2U6CgojIExvb3AgdG8gY2FsY3VsYXRlIGN1bXVsYXRpdmUgc3VtCm4gPC0gMWU2CnJlc3VsdCA8LSBudW1lcmljKG4pCmZvciAoaSBpbiAxOm4pIHsKICByZXN1bHRbaV0gPC0gc3VtKDE6aSkKfQpgYGAKCkJlbG93IGlzIHRoZSBhY3R1YWwgb3V0cHV0IGZvciBDaGF0R1BUIDRvICh3aXRoIHNvbWUgZWRpdHMgZm9yIGJyZXZpdHkgYW5kIGZvcm1hdHRpbmcpLiBOb3RpY2UgdGhlIGV4cGxhbmF0aW9ucyBnaXZpbmcgYSBub3ZpY2UgcHJvZ3JhbW1lciBhbiBvcHBvcnR1bml0eSB0byBsZWFybi4KCmBgYGAgICAgICAgICAKVGhlIHByb3ZpZGVkIFIgY29kZSBjYWxjdWxhdGVzIHRoZSBjdW11bGF0aXZlIHN1bSB1c2luZyBhIGxvb3AsIHdoaWNoIGNhbiBiZSBvcHRpbWl6ZWQgZm9yIGJldHRlciBwZXJmb3JtYW5jZS4gVXNpbmcgdmVjdG9yaXplZCBvcGVyYXRpb25zLCB3aGljaCBhcmUgaW5oZXJlbnRseSBmYXN0ZXIgaW4gUiwgY2FuIHNpZ25pZmljYW50bHkgaW1wcm92ZSB0aGUgZWZmaWNpZW5jeSBvZiB0aGlzIGNvZGUuIFNwZWNpZmljYWxseSwgdGhlIGBjdW1zdW1gIGZ1bmN0aW9uIGluIFIgaXMgZGVzaWduZWQgZm9yIHN1Y2ggdGFza3MgYW5kIGlzIG11Y2ggbW9yZSBlZmZpY2llbnQgdGhhbiBhIGxvb3AuCgpIZXJlJ3MgaG93IHlvdSBjYW4gb3B0aW1pemUgdGhlIGNvZGU6CgpgYGByCm4gPC0gMWU2CnJlc3VsdCA8LSBjdW1zdW0oMTpuKQpgYGAKCjEuICAqKlZlY3Rvcml6YXRpb24qKjogVGhlIGBjdW1zdW1gIGZ1bmN0aW9uIGNhbGN1bGF0ZXMgdGhlIGN1bXVsYXRpdmUgc3VtIG9mIGEgbnVtZXJpYyB2ZWN0b3IgaW4gYSB2ZWN0b3JpemVkIG1hbm5lci4gVGhpcyBtZWFucyB0aGF0IHRoZSBjb21wdXRhdGlvbiBpcyBwZXJmb3JtZWQgaW4gYW4gb3B0aW1pemVkIHdheSBpbnRlcm5hbGx5LCBhdm9pZGluZyB0aGUgb3ZlcmhlYWQgb2YgYW4gZXhwbGljaXQgbG9vcC4KCjIuICAqKkF2b2lkaW5nIExvb3BzKio6IExvb3BzIGluIFIsIGVzcGVjaWFsbHkgb3ZlciBsYXJnZSB2ZWN0b3JzLCBjYW4gYmUgc2xvdyBkdWUgdG8gdGhlIGludGVycHJldGVkIG5hdHVyZSBvZiBSIGFuZCB0aGUgb3ZlcmhlYWQgYXNzb2NpYXRlZCB3aXRoIHJlcGVhdGVkbHkgY2FsbGluZyBSIGZ1bmN0aW9ucy4gQnkgdXNpbmcgYGN1bXN1bWAsIHlvdSBsZXZlcmFnZSBoaWdobHkgb3B0aW1pemVkIGludGVybmFsIEMgY29kZS4KClRvIGRlbW9uc3RyYXRlIHRoZSBwZXJmb3JtYW5jZSBpbXByb3ZlbWVudCwgd2UgY2FuIGNvbXBhcmUgdGhlIGV4ZWN1dGlvbiB0aW1lIG9mIGJvdGggdGhlIGxvb3AtYmFzZWQgYXBwcm9hY2ggYW5kIHRoZSB2ZWN0b3JpemVkIGFwcHJvYWNoOgoKYGBgcgpuIDwtIDFlNgpyZXN1bHRfbG9vcCA8LSBudW1lcmljKG4pCnN5c3RlbS50aW1lKHsKICBmb3IgKGkgaW4gMTpuKSB7CiAgICByZXN1bHRfbG9vcFtpXSA8LSBzdW0oMTppKQogIH0KfSkKCnN5c3RlbS50aW1lKHsKICByZXN1bHRfY3Vtc3VtIDwtIGN1bXN1bSgxOm4pCn0pCmBgYApgYGBgCgpUaGUgZXhwbGFuYXRpb24gb2YgY29kZSBjaGFuZ2VzIG1lYW5zIHRoYXQgR2VuZXJhdGl2ZSBBSSBjYW4gYWxzbyBiZSBhIHRlYWNoZXIgYW5kIGNvYWNoLiBJdCBjYW4gZXhwbGFpbiBiZXN0IHByYWN0aWNlcyBmb3Igd3JpdGluZyBlZmZpY2llbnQgUiBjb2RlLCBpbmNsdWRpbmcgcHJvdmlkaW5nIGd1aWRhbmNlIG9uIHZlY3Rvcml6YXRpb24sIG1lbW9yeSBtYW5hZ2VtZW50LCBhbmQgdGhlIHVzZSBvZiBwYXJhbGxlbCBjb21wdXRpbmcuIEZvciBleGFtcGxlLCBhbiBBSSBhc3Npc3RhbnQgY2FuIGV4cGxhaW4gaG93IHRvIHVzZSB0aGUgYHBhcmFsbGVsYCBwYWNrYWdlIHRvIHNwZWVkIHVwIGNvbXB1dGF0aW9ucy4KCk5hdHVyYWxseSwgbm90IGFsbCBzdWdnZXN0aW9ucyBtaWdodCBiZSBjb3JyZWN0IC0tIEFJIGFzc2lzdGFudHMgZG8gaGF2ZSBhIChkZXNlcnZlZCkgcmVwdXRhdGlvbiBmb3Igd3JpdGluZyBpbmNvcnJlY3QgY29kZSBvciBnZXR0aW5nIHRoZWlyIG1hdGggd3JvbmcsIHNvIGl0IGlzIGltcG9ydGFudCB0byBkb3VibGUtY2hlY2sgYWxsIHN1Z2dlc3Rpb25zIGFuZCB0byBiZSBhIGNyaXRpY2FsIGNvbnN1bWVyIG9mIEFJIHN1Z2dlc3Rpb25zOiAqY2F2ZWF0IGVtcHRvciogYXMgdGhleSB1c2VkIHRvIHNheSBpbiBSb21lLgoKR2VuZXJhdGl2ZSBBSSBhc3Npc3RhbnRzIGJlIHBhcnRpY3VsYXJseSBoZWxwZnVsIGluIGludGVyYWN0aXZlIGRlYnVnZ2luZyBzZXNzaW9ucywgd2hlcmUgeW91IGl0ZXJhdGl2ZWx5IHJlZmluZSB5b3VyIGNvZGUgYmFzZWQgb24gdGhlIEFJ4oCZcyBmZWVkYmFjay4gWW91IGNhbiBkZXNjcmliZSB0aGUgcGVyZm9ybWFuY2UgaXNzdWVzIHlvdeKAmXJlIGVuY291bnRlcmluZywgYW5kIHRoZSBBSSB3aWxsIG9mdGVuIHN1Z2dlc3QgbW9kaWZpY2F0aW9ucyBhbmQgZnVydGhlciBvcHRpbWl6YXRpb25zLiBUaGlzIGl0ZXJhdGl2ZSBwcm9jZXNzIGhlbHBzIGluIHByb2dyZXNzaXZlbHkgaW1wcm92aW5nIHRoZSBjb2Rl4oCZcyBwZXJmb3JtYW5jZS4KCiMjIyA5LiBJbmNvcnBvcmF0ZSBDKysKCkludGVncmF0aW5nIEMrKyBjb2RlIGludG8gUiBjYW4gc2lnbmlmaWNhbnRseSBlbmhhbmNlIHBlcmZvcm1hbmNlIGZvciBjcml0aWNhbCBzZWN0aW9ucyBvZiBjb2RlLCBwYXJ0aWN1bGFybHkgd2hlbiBkZWFsaW5nIHdpdGggY29tcHV0YXRpb25hbGx5IGludGVuc2l2ZSB0YXNrcy4gUiwgd2hpbGUgcG93ZXJmdWwgZm9yIGRhdGEgYW5hbHlzaXMgYW5kIHN0YXRpc3RpY2FsIGNvbXB1dGluZywgaXMgbm90IGFzIGZhc3QgYXMgbG93LWxldmVsIGxhbmd1YWdlcyBsaWtlIEMrKyBkdWUgdG8gaXRzIGludGVycHJldGVkIG5hdHVyZSBhbmQgZHluYW1pYyB0eXBpbmcuIEJ5IG9mZmxvYWRpbmcgcGVyZm9ybWFuY2UtY3JpdGljYWwgdGFza3MgdG8gQysrLCB5b3UgY2FuIGxldmVyYWdlIHRoZSBzcGVlZCBhbmQgZWZmaWNpZW5jeSBvZiBjb21waWxlZCBjb2RlIHdoaWxlIG1haW50YWluaW5nIHRoZSBjb252ZW5pZW5jZSBvZiBSIGZvciBkYXRhIG1hbmlwdWxhdGlvbiBhbmQgdmlzdWFsaXphdGlvbi4gVGhpcyBhcHByb2FjaCBpcyBmYWNpbGl0YXRlZCBieSB0aGUgYFJjcHBgIHBhY2thZ2UsIHdoaWNoIHByb3ZpZGVzIGEgc2VhbWxlc3MgaW50ZXJmYWNlIGJldHdlZW4gUiBhbmQgQysrLgoKUiBOb3RlYm9va3MgYWxsb3cgY29kZSBibG9ja3MgaW4gdmFyaW91cyBsYW5ndWFnZXMgYW5kIHRodXMgYW4gUiBOb3RlYm9vayBjYW4gYmUgYSBtaXggb2YgbGFuZ3VhZ2VzLiBUaGUgcHJvZ3JhbW1lciBjYW4gY2hvb3NlIHRoZSAicmlnaHQgbGFuZ3VhZ2UiIGZvciBhIHByb2dyYW1taW5nIHRhc2suIEluIFIgc2NyaXB0cywgQysrIGNvZGUgY2FuIGJlIHdyYXBwZWQgYXJvdW5kIHRoZSBmdW5jdGlvbiBgY3BwRnVuY3Rpb24oKWAgZnJvbSB0aGUgKipSY3BwKiogcGFja2FnZS4KCkMrKyBpcyBhIGNvbXBpbGVkIGxhbmd1YWdlIGFuZCBleGVjdXRlcyBtdWNoIGZhc3RlciB0aGFuIFIsIGVzcGVjaWFsbHkgZm9yIGxvb3BzIGFuZCBjb21wbGV4IGNvbXB1dGF0aW9ucy4gSW4gYWRkaXRpb24sIEMrKyBhbGxvd3MgZm9yIG1vcmUgZWZmaWNpZW50IG1lbW9yeSBtYW5hZ2VtZW50IGFuZCBjYW4gaGFuZGxlIGxhcmdlIGRhdGFzZXRzIG9yIGNvbXBsZXggYWxnb3JpdGhtcyBtb3JlIGVmZmVjdGl2ZWx5LiBTbywgdXNpbmcgQysrIGZvciBwZXJmb3JtYW5jZS1jcml0aWNhbCBzZWN0aW9ucyBvZiBjb2RlIHdoaWxlIHV0aWxpemluZyBSJ3MgcmljaCBlY29zeXN0ZW0gZm9yIGRhdGEgbWFuaXB1bGF0aW9uIGFuZCBhbmFseXNpcyBwcm92aWRlcyBhIGJhbGFuY2VkIGFwcHJvYWNoIHRoYXQgbGV2ZXJhZ2VzIGVhY2ggbGFuZ3VhZ2UncyBzdHJlbmd0aC4KClRvIGJlZ2luIHVzaW5nIEMrKyBpbiBSLCB5b3UgbmVlZCB0byBpbnN0YWxsIHRoZSBgUmNwcGAgcGFja2FnZS4gVGhpcyBwYWNrYWdlIGFsbG93cyBmb3IgZWFzeSBpbnRlZ3JhdGlvbiBvZiBDKysgY29kZSB3aXRoaW4gUiBzY3JpcHRzIGFuZCBmdW5jdGlvbnMuCgpgYGB7ciBlY2hvID0gRiwgd2FybmluZz1GLCBtZXNzYWdlPUZ9CnBhY2thZ2UgPC0gIlJjcHAiCgppZiAoIXJlcXVpcmUocGFja2FnZSwgY2hhcmFjdGVyLm9ubHkgPSBUUlVFKSkgewogIGluc3RhbGwucGFja2FnZXMocGFja2FnZSwgZGVwZW5kZW5jaWVzID0gVFJVRSwgcXVpZXRseSA9IFRSVUUpCn0KCmxpYnJhcnkocGFja2FnZSwgY2hhcmFjdGVyLm9ubHkgPSBUUlVFKQpgYGAKClRoZSBgUmNwcGAgcGFja2FnZSBwcm92aWRlcyBzZXZlcmFsIGZ1bmN0aW9ucyB0byBmYWNpbGl0YXRlIHRoZSBpbnRlZ3JhdGlvbiBvZiBDKysgY29kZS4gT25lIG9mIHRoZSBtb3N0IGNvbW1vbmx5IHVzZWQgZnVuY3Rpb25zIGlzIGBjcHBGdW5jdGlvbmAsIHdoaWNoIGFsbG93cyB5b3UgdG8gZGVmaW5lIGFuZCBjb21waWxlIGEgQysrIGZ1bmN0aW9uIGRpcmVjdGx5IGluIHlvdXIgUiBzY3JpcHQuCgpDb25zaWRlciBhIHNpbXBsZSBleGFtcGxlIHdoZXJlIHdlIHdhbnQgdG8gY29tcHV0ZSB0aGUgc3VtIG9mIHNxdWFyZXMgb2YgYSBudW1lcmljIHZlY3Rvci4gSGVyZSBpcyBob3cgeW91IGNhbiBpbXBsZW1lbnQgdGhpcyBpbiBDKysgdXNpbmcgYFJjcHBgLiBOb3RlIGhvdyB0aGUgQysrIGNvZGUgaXMgYW4gYXJndW1lbnQgdG8gYW4gUiBmdW5jdGlvbiB3aGljaCB3aWxsIGNvbXBpbGUgdGhlIEMrKyBjb2RlIHVzaW5nIGFuIGluc3RhbGxlZCBDKysgY29tcGlsZXIgYW5kIHRoZW4gY3JlYXRlIGEgYmluZGluZyB0byBhbGxvdyB0aGUgQysrIGZ1bmN0aW9uIHRvIGJlIGNhbGxlZCBmcm9tIFIuCgpUaGUgZnVuY3Rpb24gYGNwcEZ1bmN0aW9uKClgIGNhbGxzIHRoZSBDKysgY29tcGlsZXIsIGNvbXBpbGVzIHRoZSBjb2RlICh3aGljaCBjYW4gdGFrZSBzb21lIHRpbWUpLCBhbmQgdGhlbiBjcmVhdGVzIGEgbGFuZ3VhZ2UgYmluZGluZyBzbyB0aGUgY29tcGlsZWQgQysrIGZ1bmN0aW9uIGNhbiBiZSBjYWxsZWQgZnJvbSBSLgoKKipDKysgRnVuY3Rpb246KioKCmBgYHtyIGNyZWF0ZUNwcEZ1bmN9CmxpYnJhcnkoUmNwcCkKCmNwcEZ1bmN0aW9uKCcKZG91YmxlIHN1bU9mU3F1YXJlcyhOdW1lcmljVmVjdG9yIHgpIHsKICBpbnQgbiA9IHguc2l6ZSgpOwogIGRvdWJsZSBzdW0gPSAwOwogIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICBzdW0gKz0geFtpXSAqIHhbaV07CiAgfQogIHJldHVybiBzdW07Cn0nKQpgYGAKCioqVXNpbmcgdGhlIEMrKyBGdW5jdGlvbiBpbiBSOioqCgpgYGB7ciB1c2VDcHBGdW5jfQojIENyZWF0aW5nIGEgbnVtZXJpYyB2ZWN0b3IKdmVjIDwtIHJub3JtKDFlNikKCiMgQ2FsbGluZyB0aGUgQysrIGZ1bmN0aW9uIGZyb20gUgpyZXN1bHQgPC0gc3VtT2ZTcXVhcmVzKHZlYykKcHJpbnQocmVzdWx0KQpgYGAKCkluIHRoaXMgZXhhbXBsZSwgdGhlIEMrKyBmdW5jdGlvbiBgc3VtT2ZTcXVhcmVzYCBjb21wdXRlcyB0aGUgc3VtIG9mIHNxdWFyZXMgb2YgdGhlIGVsZW1lbnRzIGluIHRoZSBpbnB1dCB2ZWN0b3IgYHhgLiBUaGlzIGZ1bmN0aW9uIGlzIHRoZW4gY2FsbGVkIGZyb20gUiwgZGVtb25zdHJhdGluZyB0aGUgc2VhbWxlc3MgaW50ZWdyYXRpb24gb2YgUiBhbmQgQysrLiBXcml0aW5nIG1vcmUgY29tcGxleCBDKysgY29kZSBpcyBiZXN0IGRvbmUgYnkgd3JpdGluZyBhbiBlbnRpcmUgcGFja2FnZSBpbiBDKysgYnV0IHRoYXQgaXMgYmV5b25kIHRoZSBzY29wZSBvZiB0aGlzIGxlc3Nvbi4KCkZvciBhIG1vcmUgY29tcGxleCBleGFtcGxlLCBjb25zaWRlciBtYXRyaXggbXVsdGlwbGljYXRpb24sIGEgY29tcHV0YXRpb25hbGx5IGludGVuc2l2ZSB0YXNrIHRoYXQgY2FuIGJlbmVmaXQgZ3JlYXRseSBmcm9tIEMrKyBvcHRpbWl6YXRpb24uCgoqKkMrKyBGdW5jdGlvbiBmb3IgTWF0cml4IE11bHRpcGxpY2F0aW9uOioqCgpgYGB7cn0KY3BwRnVuY3Rpb24oJwpOdW1lcmljTWF0cml4IG1hdE11bHQoTnVtZXJpY01hdHJpeCBBLCBOdW1lcmljTWF0cml4IEIpIHsKICBpbnQgbiA9IEEubnJvdygpOwogIGludCBrID0gQS5uY29sKCk7CiAgaW50IG0gPSBCLm5jb2woKTsKICBOdW1lcmljTWF0cml4IEMobiwgbSk7CiAgCiAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgIGZvciAoaW50IGogPSAwOyBqIDwgbTsgKytqKSB7CiAgICAgIGZvciAoaW50IGwgPSAwOyBsIDwgazsgKytsKSB7CiAgICAgICAgQyhpLGopICs9IEEoaSxsKSAqIEIobCxqKTsKICAgICAgfQogICAgfQogIH0KICByZXR1cm4gQzsKfScpCmBgYAoKKipVc2luZyB0aGUgQysrIEZ1bmN0aW9uIGluIFI6KioKCmBgYHtyfQojIGNyZWF0ZSB0d28gbGFyZ2UgbWF0cmljZXMKQSA8LSBtYXRyaXgocm5vcm0oMWU2KSwgbnJvdyA9IDEwMDApCkIgPC0gbWF0cml4KHJub3JtKDFlNiksIG5yb3cgPSAxMDAwKQoKIyBwZXJmb3JtIG1hdHJpeCBtdWx0aXBsaWNhdGlvbiB1c2luZyB0aGUgQysrIGZ1bmN0aW9uCnJlc3VsdCA8LSBtYXRNdWx0KEEsIEIpCmBgYAoKSW4gdGhpcyBleGFtcGxlLCB0aGUgYG1hdE11bHRgIGZ1bmN0aW9uIG11bHRpcGxpZXMgdHdvIG1hdHJpY2VzIGBBYCBhbmQgYEJgLiBUaGUgQysrIGltcGxlbWVudGF0aW9uIGlzIHNpZ25pZmljYW50bHkgZmFzdGVyIHRoYW4gYSBwdXJlIFIgaW1wbGVtZW50YXRpb24sIGVzcGVjaWFsbHkgZm9yIGxhcmdlIG1hdHJpY2VzLgoKIyMgMTAuIFNhdmUgTGFyZ2UgT2JqZWN0cwoKSW4gUiwgeW91IGNhbiBzYXZlIGFueSBkYXRhIG9iamVjdCwgc3VjaCBhcyBhIGRhdGEgZnJhbWUsIHRvIGFuIFIgb2JqZWN0IGZpbGUgKCouUkRhdGEqKSB1c2luZyB0aGUgYHNhdmUoKWAgZnVuY3Rpb24gYW5kIHRoZW4gcmVzdG9yZSBpdCB1c2luZyB0aGUgYGxvYWQoKWAgZnVuY3Rpb24uIFRoaXMgYXBwcm9hY2ggaXMgdXNlZnVsIGZvciBwcmVzZXJ2aW5nIHRoZSBzdGF0ZSBvZiB5b3VyIGRhdGEgYmV0d2VlbiBzZXNzaW9ucywgZXNwZWNpYWxseSB3aGVuIHdvcmtpbmcgd2l0aCBsYXJnZSBkYXRhc2V0cyB0aGF0IHJlcXVpcmUgc2lnbmlmaWNhbnQgcHJvY2Vzc2luZyB0aW1lLiBJdCBtZWFucyB0aGF0IHlvdSBjcmVhdGUgdGhlIGRhdGEgb2JqZWN0IG9uY2UsIHNhdmUgaXQgdG8gYW4gb2JqZWN0IGZpbGUsIGFuZCB0aGVuIHJlc3RvcmUgaXQgZnJvbSB0aGUgZmlsZSB3aGVuIG5lZWRlZCByYXRoZXIgdGhhbiBjcmUtY3JlYXRpbmcgaXQuCgpGaXJzdCwgY3JlYXRlIGEgZGF0YSBmcmFtZSwgdGhlbiBzYXZlIHRoZSBkYXRhIGZyYW1lIHRvIGFuIFIgb2JqZWN0IGZpbGUgdXNpbmcgdGhlIGBzYXZlYCBmdW5jdGlvbi4gV2hlbiBuZWVkZWQgbGF0ZXIgaW4gYSBuZXcgc2Vzc2lvbiwgY2hlY2sgaWYgdGhlIG9iamVjdCBleGlzdHMgYW5kLCBpZiBub3QsIGxvYWQgaXQuIEJlZm9yZSByZXN0b3JpbmcgdGhlIGRhdGEgZnJhbWUsIGNoZWNrIGlmIHRoZSBvYmplY3QgZmlsZSBleGlzdHMuIElmIHRoZSBmaWxlIGV4aXN0cywgbG9hZCB0aGUgZGF0YSBmcmFtZSB1c2luZyB0aGUgYGxvYWRgIGZ1bmN0aW9uLCBvdGhlcndpc2UgY3JlYXRlIHRoZSBkYXRhIGZyYW1lLiBUaGUgY29kZSBiZWxvdyBkZW1vbnN0cmF0ZXMgdGhpcy4KCmBgYHtyfQojIGxvYWQgdGhlIGRhdGEKZGYudHhucyA8LSByZWFkLmNzdignY3VzdG9tZXJ0eG5kYXRhLmNzdicpCgojIyMgZG8gc29tZSBpbnRlbnNpdmUgcHJvY2Vzc2luZyB0aGF0IHRha2Ugc2lnbmlmaWNhbnQgdGltZQojIyMgLi4uCgojIHNhdmUgdGhlIGRhdGEgZnJhbWUgdG8gYW4gUiBvYmplY3QgZmlsZQpzYXZlKGRmLnR4bnMsIGZpbGUgPSAiZGZfdHhuRGF0YS5SRGF0YSIpCgojIyMgZm9yIHRlc3Rpbmcgd2Ugd2lsbCByZW1vdmUgdGhlIG9iamVjdCBmcm9tIG1lbW9yeQpybShkZi50eG5zKQoKYGBgCgpUaGUgY29kZSBiZWxvdyBjaGVja3MgaWYgdGhlIG9iamVjdCBmaWxlIGV4aXN0cywgYW5kLCBpZiBpdCBkb2Vzbid0LCByZXN0b3JlcyB0aGUgZGF0YSBmcmFtZSBmcm9tIHRoZSBvYmplY3QgZmlsZS4gTm90aWNlIHRoYXQgdGhlIG9iamVjdCBmaWxlIGNvbnRhaW5zIHRoZSBkYXRhIGZyYW1lJ3MgbmFtZSBhcyB3ZWxsLgoKYGBge3J9CiMgZmlsZSBwYXRoIGFuZCBuYW1lIG9mIHRoZSBvYmplY3QgZmlsZQpmaWxlX3BhdGggPC0gImRmX3R4bkRhdGEuUkRhdGEiCgojIHJlc3RvcmUgdGhlIGRhdGEgZnJhbWUgZnJvbSBpdHMgZmlsZSAtLSBpZiBpdCBleGlzdHMKaWYgKGZpbGUuZXhpc3RzKGZpbGVfcGF0aCkpIHsKICBsb2FkKGZpbGVfcGF0aCkKfSBlbHNlIHsKICAjIGNyZWF0ZSB0aGUgZGF0YSBmcmFtZQogICMgLi4uCn0KCiMgZGlzcGxheSB0aGUgZmlyc3QgZmV3IHJvd3Mgb2YgdGhlIHJlc3RvcmVkIGRhdGEgZnJhbWUKaGVhZChkZi50eG5zLCAzKQoKYGBgCgojIyBTdW1tYXJ5CgpJbiBzdW1tYXJ5LCBvcHRpbWl6aW5nIFIgY29kZSBwZXJmb3JtYW5jZSBpbnZvbHZlcyBhIG11bHRpZmFjZXRlZCBhcHByb2FjaC4gQnkgYWRvcHRpbmcgZWZmaWNpZW50IGRhdGEgc3RydWN0dXJlcyBsaWtlIGBkYXRhLnRhYmxlYCwgbGV2ZXJhZ2luZyB2ZWN0b3JpemVkIG9wZXJhdGlvbnMsIG1hbmFnaW5nIG1lbW9yeSBlZmZlY3RpdmVseSwgdXRpbGl6aW5nIHBhcmFsbGVsIGNvbXB1dGluZywgYW5kIHByb2ZpbGluZyB5b3VyIGNvZGUsIHlvdSBjYW4gYWNoaWV2ZSBzaWduaWZpY2FudCBydW4tdGltZSBpbXByb3ZlbWVudHMuIFRoZXNlIHRlY2huaXF1ZXMgYXJlIG5vdCBvbmx5IGVzc2VudGlhbCBmb3IgaGFuZGxpbmcgbGFyZ2UgZGF0YXNldHMgYnV0IGFsc28gZm9yIGVuc3VyaW5nIHRoYXQgeW91ciBjb21wdXRhdGlvbnMgYXJlIGJvdGggZmFzdCBhbmQgc2NhbGFibGUsIGFuIGVzc2VudGlhbCByZXF1aXJlbWVudHMgZm9yIG1hY2hpbmUgbGVhcm5pbmcsIHN0YXRpc3RpY2FsIGNvbXB1dGluZywgYW5kIGRhdGEgYXBwbGljYXRpb25zLgoKVGhlIGB3aGljaCgpYCBmdW5jdGlvbiBpbiBSIGlzIGEgaGlnaGx5IGVmZmljaWVudCBhbHRlcm5hdGl2ZSB0byBsb29wcyBmb3IgY29uZGl0aW9uYWwgc2VhcmNoZXMuIEl0IHNpbXBsaWZpZXMgdGhlIHByb2Nlc3Mgb2YgaWRlbnRpZnlpbmcgaW5kaWNlcyB3aGVyZSBhIGNvbmRpdGlvbiBpcyBtZXQsIHByb3ZpZGluZyBib3RoIHBlcmZvcm1hbmNlIGJlbmVmaXRzIGFuZCBpbXByb3ZlZCBjb2RlIHJlYWRhYmlsaXR5LiBCeSBsZXZlcmFnaW5nIGB3aGljaCgpYCwgeW91IGNhbiB3cml0ZSBtb3JlIGVmZmljaWVudCBhbmQgY29uY2lzZSBSIGNvZGUgZm9yIHRhc2tzIGludm9sdmluZyBjb25kaXRpb25hbCBzdWJzZXR0aW5nIGFuZCBmaWx0ZXJpbmcuCgpHZW5lcmF0aXZlIEFJIGFzc2lzdGFudHMgbGlrZSBDaGF0R1BUIGFuZCBDbGF1ZGUgY2FuIGJlIGhlbHBmdWwgaW4gaWRlbnRpZnlpbmcgYW5kIHJlc29sdmluZyBwZXJmb3JtYW5jZSBpc3N1ZXMgaW4gUiBjb2RlLiBGb3IgdGhlIGNyaXRpY2FsIHByb2dyYW1tZXIsIHRoZXkgY2FuIHByb3ZpZGUgY29kZSByZXZpZXdzLCBzdWdnZXN0IG9wdGltaXphdGlvbnMsIHJlY29tbWVuZCBlZmZpY2llbnQgZGF0YSBzdHJ1Y3R1cmVzLCBndWlkZSB5b3UgdGhyb3VnaCBwcm9maWxpbmcgdGVjaG5pcXVlcywgYW5kIG9mZmVyIGluc2lnaHRzIGludG8gYmVzdCBwcmFjdGljZXMuCgpCeSBpbnRlZ3JhdGluZyBDKysgY29kZSBpbnRvIFIgdXNpbmcgdGhlIGBSY3BwYCBwYWNrYWdlLCB5b3UgY2FuIGFjaGlldmUgc3Vic3RhbnRpYWwgcGVyZm9ybWFuY2UgaW1wcm92ZW1lbnRzIGZvciBjb21wdXRhdGlvbmFsbHkgaW50ZW5zaXZlIHRhc2tzLiBUaGlzIGFwcHJvYWNoIGFsbG93cyB5b3UgdG8gdXNlIFIgZm9yIGRhdGEgbWFuaXB1bGF0aW9uIHdpdGggdGhlIHRhcmdldGVkIGVmZmljaWVuY3kgb2YgQysrLgoKIyMgRmlsZXMgJiBSZXNvdXJjZXMKCmBgYHtyIHppcEZpbGVzLCBlY2hvPUZBTFNFfQp6aXBOYW1lID0gc3ByaW50ZigiTGVzc29uRmlsZXMtJXMtJXMuemlwIiwgCiAgICAgICAgICAgICAgICAgcGFyYW1zJGNhdGVnb3J5LAogICAgICAgICAgICAgICAgIHBhcmFtcyRudW1iZXIpCgp0ZXh0QUxpbmsgPSBwYXN0ZTAoIkFsbCBGaWxlcyBmb3IgTGVzc29uICIsIAogICAgICAgICAgICAgICBwYXJhbXMkY2F0ZWdvcnksIi4iLHBhcmFtcyRudW1iZXIpCgojIGRvd25sb2FkRmlsZXNMaW5rKCkgaXMgaW5jbHVkZWQgZnJvbSBfaW5zZXJ0MkRCLlIKa25pdHI6OnJhd19odG1sKGRvd25sb2FkRmlsZXNMaW5rKCIuIiwgemlwTmFtZSwgdGV4dEFMaW5rKSkKYGBgCgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCiMjIFJlZmVyZW5jZXMKClRCRAoKIyMgRXJyYXRhCgpbTGV0IHVzIGtub3ddKGh0dHBzOi8vZm9ybS5qb3Rmb3JtLmNvbS8yMTIxODcwNzI3ODQxNTcpe3RhcmdldD0iX2JsYW5rIn0uCg==