Besides Deep Dream, another major development in deep learning-driven image modification that happened in the summer of 2015 is neural style transfer, introduced by Leon Gatys et al. The neural style transfer algorithm has undergone many refinements and spawned many variations since its original introduction, including a viral smartphone app, called Prisma. For simplicity, this section focuses on the formulation described in the original paper.
Neural style transfer consists in applying the “style” of a reference image to a target image, while conserving the “content” of the target image:
What is meant by “style” is essentially textures, colors, and visual patterns in the image, at various spatial scales, while the “content” is the higher-level macrostructure of the image. For instance, blue-and-yellow circular brush strokes are considered to be the “style” in the above example using Starry Night by Van Gogh, while the buildings in the Tuebingen photograph are considered to be the “content”.
The idea of style transfer, tightly related to that of texture generation, has had a long history in the image processing community prior to the development of neural style transfer in 2015. However, as it turned out, the deep learning-based implementations of style transfer offered results unparalleled by what could be previously achieved with classical computer vision techniques, and triggered an amazing renaissance in creative applications of computer vision.
The key notion behind implementing style transfer is same idea that is central to all deep learning algorithms: we define a loss function to specify what we want to achieve, and we minimize this loss. We know what we want to achieve: conserve the “content” of the original image, while adopting the “style” of the reference image. If we were able to mathematically define content and style, then an appropriate loss function to minimize would be the following:
A fundamental observation made by Gatys et al is that deep convolutional neural networks offer precisely a way to mathematically defined the style
and content
functions. Let’s see how.
Neural style transfer in Keras
Neural style transfer can be implemented using any pre-trained convnet. Here we will use the VGG19 network, used by Gatys et al in their paper. VGG19 is a simple variant of the VGG16 network we introduced in Chapter 5, with three more convolutional layers.
This is our general process:
- Set up a network that will compute VGG19 layer activations for the style reference image, the target image, and the generated image at the same time.
- Use the layer activations computed over these three images to define the loss function described above, which we will minimize in order to achieve style transfer.
- Set up a gradient descent process to minimize this loss function.
Let’s start by defining the paths to the two images we consider: the style reference image and the target image. To make sure that all images processed share similar sizes (widely different sizes would make style transfer more difficult), we will later resize them all to a shared height of 400px.
library(keras)
# This is the path to the image you want to transform.
target_image_path <- "style_transfer/portrait.png"
# This is the path to the style image.
style_reference_image_path <- "style_transfer/transfer_style_reference.png"
# Dimensions of the generated picture.
img <- image_load(target_image_path)
Using TensorFlow backend.
2017-11-28 15:39:32.299249: I tensorflow/core/platform/cpu_feature_guard.cc:137] Your CPU supports instructions that this TensorFlow binary was not compiled to use: SSE4.1 SSE4.2 AVX AVX2 FMA
2017-11-28 15:39:35.368769: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:892] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2017-11-28 15:39:35.369155: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1030] Found device 0 with properties:
name: Tesla K80 major: 3 minor: 7 memoryClockRate(GHz): 0.8235
pciBusID: 0000:00:1e.0
totalMemory: 11.17GiB freeMemory: 11.10GiB
2017-11-28 15:39:35.369189: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1120] Creating TensorFlow device (/device:GPU:0) -> (device: 0, name: Tesla K80, pci bus id: 0000:00:1e.0, compute capability: 3.7)
width <- img$size[[1]]
height <- img$size[[2]]
img_nrows <- 400
img_ncols <- as.integer(width * img_nrows / height)
We will need some auxiliary functions for loading, pre-processing and post-processing the images that will go in and out of the VGG19 convnet:
preprocess_image <- function(path) {
img <- image_load(path, target_size = c(img_nrows, img_ncols)) %>%
image_to_array() %>%
array_reshape(c(1, dim(.)))
imagenet_preprocess_input(img)
}
deprocess_image <- function(x) {
x <- x[1,,,]
# Remove zero-center by mean pixel
x[,,1] <- x[,,1] + 103.939
x[,,2] <- x[,,2] + 116.779
x[,,3] <- x[,,3] + 123.68
# 'BGR'->'RGB'
x <- x[,,c(3,2,1)]
x[x > 255] <- 255
x[x < 0] <- 0
x[] <- as.integer(x)/255
x
}
Let’s set up the VGG19 network. It takes as input a batch of three images: the style-reference image, the target image, and a placeholder that will contain the generated image. A placeholder is a symbolic tensor, the values of which are provided externally via R arrays. The style-reference and target image are static and thus defined using k_constant
, whereas the values contained in the placeholder of the generated image will change over time.
target_image <- k_constant(preprocess_image(target_image_path))
style_reference_image <- k_constant(
preprocess_image(style_reference_image_path)
)
# This placeholder will contain our generated image
combination_image <- k_placeholder(c(1, img_nrows, img_ncols, 3))
# We combine the 3 images into a single batch
input_tensor <- k_concatenate(list(target_image, style_reference_image,
combination_image), axis = 1)
# We build the VGG19 network with our batch of 3 images as input.
# The model will be loaded with pre-trained ImageNet weights.
model <- application_vgg19(input_tensor = input_tensor,
weights = "imagenet",
include_top = FALSE)
2017-11-28 15:39:36.704922: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1120] Creating TensorFlow device (/device:GPU:0) -> (device: 0, name: Tesla K80, pci bus id: 0000:00:1e.0, compute capability: 3.7)
cat("Model loaded\n")
Model loaded
Let’s define the content loss, meant to make sure that the top layer of the VGG19 convnet will have a similar view of the target image and the generated image:
content_loss <- function(base, combination) {
k_sum(k_square(combination - base))
}
Now, here’s the style loss. It leverages an auxiliary function to compute the Gram matrix of an input matrix, i.e. a map of the correlations found in the original feature matrix.
gram_matrix <- function(x) {
features <- k_batch_flatten(k_permute_dimensions(x, c(3, 1, 2)))
gram <- k_dot(features, k_transpose(features))
gram
}
style_loss <- function(style, combination){
S <- gram_matrix(style)
C <- gram_matrix(combination)
channels <- 3
size <- img_nrows*img_ncols
k_sum(k_square(S - C)) / (4 * channels^2 * size^2)
}
To these two loss components, we add a third one, the “total variation loss”. It is meant to encourage spatial continuity in the generated image, thus avoiding overly pixelated results. You could interpret it as a regularization loss.
total_variation_loss <- function(x) {
y_ij <- x[,1:(img_nrows - 1L), 1:(img_ncols - 1L),]
y_i1j <- x[,2:(img_nrows), 1:(img_ncols - 1L),]
y_ij1 <- x[,1:(img_nrows - 1L), 2:(img_ncols),]
a <- k_square(y_ij - y_i1j)
b <- k_square(y_ij - y_ij1)
k_sum(k_pow(a + b, 1.25))
}
The loss that we minimize is a weighted average of these three losses. To compute the content loss, we only leverage one top layer, the block5_conv2
layer, while for the style loss we use a list of layers than spans both low-level and high-level layers. We add the total variation loss at the end.
Depending on the style reference image and content image you are using, you will likely want to tune the content_weight
coefficient, the contribution of the content loss to the total loss. A higher content_weight
means that the target content will be more recognizable in the generated image.
# Named list mapping layer names to activation tensors
outputs_dict <- lapply(model$layers, `[[`, "output")
names(outputs_dict) <- lapply(model$layers, `[[`, "name")
# Name of layer used for content loss
content_layer <- "block5_conv2"
# Name of layers used for style loss
style_layers = c("block1_conv1", "block2_conv1",
"block3_conv1", "block4_conv1",
"block5_conv1")
# Weights in the weighted average of the loss components
total_variation_weight <- 1e-4
style_weight <- 1.0
content_weight <- 0.025
# Define the loss by adding all components to a `loss` variable
loss <- k_variable(0.0)
layer_features <- outputs_dict[[content_layer]]
target_image_features <- layer_features[1,,,]
combination_features <- layer_features[3,,,]
loss <- loss + content_weight * content_loss(target_image_features,
combination_features)
for (layer_name in style_layers){
layer_features <- outputs_dict[[layer_name]]
style_reference_features <- layer_features[2,,,]
combination_features <- layer_features[3,,,]
sl <- style_loss(style_reference_features, combination_features)
loss <- loss + ((style_weight / length(style_layers)) * sl)
}
loss <- loss +
(total_variation_weight * total_variation_loss(combination_image))
Finally, we set up the gradient-descent process. In the original Gatys et al. paper, optimization is performed using the L-BFGS algorithm, so that is also what you’ll use here. This is a key difference from the DeepDream example in section 8.2. The L-BFGS algorithm is available via the optim()
function, but there are two slight limitations with the optim()
implementation:
- It requires that you pass the value of the loss function and the value of the gradients as two separate functions.
- It can only be applied to flat vectors, whereas you have a 3D image array.
It would be inefficient to compute the value of the loss function and the value of the gradients independently, because doing so would lead to a lot of redundant computation between the two; the process would be almost twice as slow as computing them jointly. To bypass this, you’ll set up an R6 class named Evaluator
that computes both the loss value and the gradients value at once, returns the loss value when called the first time, and caches the gradients for the next call.
# Get the gradients of the generated image wrt the loss
grads <- k_gradients(loss, combination_image)[[1]]
# Function to fetch the values of the current loss and the current gradients
fetch_loss_and_grads <- k_function(list(combination_image), list(loss, grads))
eval_loss_and_grads <- function(image) {
image <- array_reshape(image, c(1, img_nrows, img_ncols, 3))
outs <- fetch_loss_and_grads(list(image))
list(
loss_value = outs[[1]],
grad_values = array_reshape(outs[[2]], dim = length(outs[[2]]))
)
}
library(R6)
Evaluator <- R6Class("Evaluator",
public = list(
loss_value = NULL,
grad_values = NULL,
initialize = function() {
self$loss_value <- NULL
self$grad_values <- NULL
},
loss = function(x){
loss_and_grad <- eval_loss_and_grads(x)
self$loss_value <- loss_and_grad$loss_value
self$grad_values <- loss_and_grad$grad_values
self$loss_value
},
grads = function(x){
grad_values <- self$grad_values
self$loss_value <- NULL
self$grad_values <- NULL
grad_values
}
)
)
evaluator <- Evaluator$new()
Finally, you can run the gradient-ascent process using the L-BFGS algorithm, plotting the current generated image at each iteration of the algorithm (here, a single iteration represents 20 steps of gradient ascent).
iterations <- 20
dms <- c(1, img_nrows, img_ncols, 3)
# This is the initial state: the target image.
x <- preprocess_image(target_image_path)
# Note that optim can only process flat vectors.
x <- array_reshape(x, dim = length(x))
for (i in 1:iterations) {
# Runs L-BFGS over the pixels of the generated image to minimize the neural style loss.
opt <- optim(
array_reshape(x, dim = length(x)),
fn = evaluator$loss,
gr = evaluator$grads,
method = "L-BFGS-B",
control = list(maxit = 15)
)
cat("Loss:", opt$value, "\n")
image <- x <- opt$par
image <- array_reshape(image, dms)
im <- deprocess_image(image)
plot(as.raster(im))
}
Keep in mind that what this technique achieves is merely a form of image re-texturing, or texture transfer. It will work best with style reference images that are strongly textured and highly self-similar, and with content targets that don’t require high levels of details in order to be recognizable. It would typically not be able to achieve fairly abstract feats such as “transferring the style of one portrait to another”. The algorithm is closer to classical signal processing than to AI, so don’t expect it to work like magic!
Additionally, do note that running this style transfer algorithm is quite slow. However, the transformation operated by our setup is simple enough that it can be learned by a small, fast feedforward convnet as well – as long as you have appropriate training data available. Fast style transfer can thus be achieved by first spending a lot of compute cycles to generate input-output training examples for a fixed style reference image, using the above method, and then training a simple convnet to learn this style-specific transformation. Once that is done, stylizing a given image is instantaneous: it’s a just a forward pass of this small convnet.
LS0tCnRpdGxlOiAiTmV1cmFsIHN0eWxlIHRyYW5zZmVyIgpvdXRwdXQ6IAogIGh0bWxfbm90ZWJvb2s6IAogICAgdGhlbWU6IGNlcnVsZWFuCiAgICBoaWdobGlnaHQ6IHRleHRtYXRlCi0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldCh3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSkKYGBgCgoqKioKClRoaXMgbm90ZWJvb2sgY29udGFpbnMgdGhlIGNvZGUgc2FtcGxlcyBmb3VuZCBpbiBDaGFwdGVyIDgsIFNlY3Rpb24gMyBvZiBbRGVlcCBMZWFybmluZyB3aXRoIFJdKGh0dHBzOi8vd3d3Lm1hbm5pbmcuY29tL2Jvb2tzL2RlZXAtbGVhcm5pbmctd2l0aC1yKS4gTm90ZSB0aGF0IHRoZSBvcmlnaW5hbCB0ZXh0IGZlYXR1cmVzIGZhciBtb3JlIGNvbnRlbnQsIGluIHBhcnRpY3VsYXIgZnVydGhlciBleHBsYW5hdGlvbnMgYW5kIGZpZ3VyZXM6IGluIHRoaXMgbm90ZWJvb2ssIHlvdSB3aWxsIG9ubHkgZmluZCBzb3VyY2UgY29kZSBhbmQgcmVsYXRlZCBjb21tZW50cy4KCioqKgoKQmVzaWRlcyBEZWVwIERyZWFtLCBhbm90aGVyIG1ham9yIGRldmVsb3BtZW50IGluIGRlZXAgbGVhcm5pbmctZHJpdmVuIGltYWdlIG1vZGlmaWNhdGlvbiB0aGF0IGhhcHBlbmVkIGluIHRoZSBzdW1tZXIgb2YgMjAxNSBpcyBuZXVyYWwgc3R5bGUgdHJhbnNmZXIsIGludHJvZHVjZWQgYnkgTGVvbiBHYXR5cyBldCBhbC4gVGhlIG5ldXJhbCBzdHlsZSB0cmFuc2ZlciBhbGdvcml0aG0gaGFzIHVuZGVyZ29uZSBtYW55IHJlZmluZW1lbnRzIGFuZCBzcGF3bmVkIG1hbnkgdmFyaWF0aW9ucyBzaW5jZSBpdHMgb3JpZ2luYWwgaW50cm9kdWN0aW9uLCBpbmNsdWRpbmcgYSB2aXJhbCBzbWFydHBob25lIGFwcCwgY2FsbGVkIFByaXNtYS4gRm9yIHNpbXBsaWNpdHksIHRoaXMgc2VjdGlvbiBmb2N1c2VzIG9uIHRoZSBmb3JtdWxhdGlvbiBkZXNjcmliZWQgaW4gdGhlIG9yaWdpbmFsIHBhcGVyLgoKTmV1cmFsIHN0eWxlIHRyYW5zZmVyIGNvbnNpc3RzIGluIGFwcGx5aW5nIHRoZSAic3R5bGUiIG9mIGEgcmVmZXJlbmNlIGltYWdlIHRvIGEgdGFyZ2V0IGltYWdlLCB3aGlsZSBjb25zZXJ2aW5nIHRoZSAiY29udGVudCIgb2YgdGhlIHRhcmdldCBpbWFnZToKCiFbc3R5bGUgdHJhbnNmZXJdKGh0dHBzOi8vczMuYW1hem9uYXdzLmNvbS9ib29rLmtlcmFzLmlvL2ltZy9jaDgvc3R5bGVfdHJhbnNmZXIucG5nKQoKV2hhdCBpcyBtZWFudCBieSAic3R5bGUiIGlzIGVzc2VudGlhbGx5IHRleHR1cmVzLCBjb2xvcnMsIGFuZCB2aXN1YWwgcGF0dGVybnMgaW4gdGhlIGltYWdlLCBhdCB2YXJpb3VzIHNwYXRpYWwgc2NhbGVzLCB3aGlsZSB0aGUgImNvbnRlbnQiIGlzIHRoZSBoaWdoZXItbGV2ZWwgbWFjcm9zdHJ1Y3R1cmUgb2YgdGhlIGltYWdlLiBGb3IgaW5zdGFuY2UsIGJsdWUtYW5kLXllbGxvdyBjaXJjdWxhciBicnVzaCBzdHJva2VzIGFyZSBjb25zaWRlcmVkIHRvIGJlIHRoZSAic3R5bGUiIGluIHRoZSBhYm92ZSBleGFtcGxlIHVzaW5nIFN0YXJyeSBOaWdodCBieSBWYW4gR29naCwgd2hpbGUgdGhlIGJ1aWxkaW5ncyBpbiB0aGUgVHVlYmluZ2VuIHBob3RvZ3JhcGggYXJlIGNvbnNpZGVyZWQgdG8gYmUgdGhlICJjb250ZW50Ii4KClRoZSBpZGVhIG9mIHN0eWxlIHRyYW5zZmVyLCB0aWdodGx5IHJlbGF0ZWQgdG8gdGhhdCBvZiB0ZXh0dXJlIGdlbmVyYXRpb24sIGhhcyBoYWQgYSBsb25nIGhpc3RvcnkgaW4gdGhlIGltYWdlIHByb2Nlc3NpbmcgY29tbXVuaXR5IHByaW9yIHRvIHRoZSBkZXZlbG9wbWVudCBvZiBuZXVyYWwgc3R5bGUgdHJhbnNmZXIgaW4gMjAxNS4gSG93ZXZlciwgYXMgaXQgdHVybmVkIG91dCwgdGhlIGRlZXAgbGVhcm5pbmctYmFzZWQgaW1wbGVtZW50YXRpb25zIG9mIHN0eWxlIHRyYW5zZmVyIG9mZmVyZWQgcmVzdWx0cyB1bnBhcmFsbGVsZWQgYnkgd2hhdCBjb3VsZCBiZSBwcmV2aW91c2x5IGFjaGlldmVkIHdpdGggY2xhc3NpY2FsIGNvbXB1dGVyIHZpc2lvbiB0ZWNobmlxdWVzLCBhbmQgdHJpZ2dlcmVkIGFuIGFtYXppbmcgcmVuYWlzc2FuY2UgaW4gY3JlYXRpdmUgYXBwbGljYXRpb25zIG9mIGNvbXB1dGVyIHZpc2lvbi4KClRoZSBrZXkgbm90aW9uIGJlaGluZCBpbXBsZW1lbnRpbmcgc3R5bGUgdHJhbnNmZXIgaXMgc2FtZSBpZGVhIHRoYXQgaXMgY2VudHJhbCB0byBhbGwgZGVlcCBsZWFybmluZyBhbGdvcml0aG1zOiB3ZSBkZWZpbmUgYSBsb3NzIGZ1bmN0aW9uIHRvIHNwZWNpZnkgd2hhdCB3ZSB3YW50IHRvIGFjaGlldmUsIGFuZCB3ZSBtaW5pbWl6ZSB0aGlzIGxvc3MuIFdlIGtub3cgd2hhdCB3ZSB3YW50IHRvIGFjaGlldmU6IGNvbnNlcnZlIHRoZSAiY29udGVudCIgb2YgdGhlIG9yaWdpbmFsIGltYWdlLCB3aGlsZSBhZG9wdGluZyB0aGUgInN0eWxlIiBvZiB0aGUgcmVmZXJlbmNlIGltYWdlLiBJZiB3ZSB3ZXJlIGFibGUgdG8gbWF0aGVtYXRpY2FsbHkgZGVmaW5lIGNvbnRlbnQgYW5kIHN0eWxlLCB0aGVuIGFuIGFwcHJvcHJpYXRlIGxvc3MgZnVuY3Rpb24gdG8gbWluaW1pemUgd291bGQgYmUgdGhlIGZvbGxvd2luZzoKCmBgYApsb3NzIDwtIGRpc3RhbmNlKHN0eWxlKHJlZmVyZW5jZV9pbWFnZSkgLSBzdHlsZShnZW5lcmF0ZWRfaW1hZ2UpKSArCiAgICAgICAgZGlzdGFuY2UoY29udGVudChvcmlnaW5hbF9pbWFnZSkgLSBjb250ZW50KGdlbmVyYXRlZF9pbWFnZSkpCmBgYAoKV2hlcmUgYGRpc3RhbmNlYCBpcyBhIG5vcm0gZnVuY3Rpb24gc3VjaCBhcyB0aGUgTDIgbm9ybSwgYGNvbnRlbnRgIGlzIGEgZnVuY3Rpb24gdGhhdCB0YWtlcyBhbiBpbWFnZSBhbmQgY29tcHV0ZXMgYSByZXByZXNlbnRhdGlvbiBvZiBpdHMgImNvbnRlbnQiLCBhbmQgYHN0eWxlYCBpcyBhIGZ1bmN0aW9uIHRoYXQgdGFrZXMgYW4gaW1hZ2UgYW5kIGNvbXB1dGVzIGEgcmVwcmVzZW50YXRpb24gb2YgaXRzICJzdHlsZSIuCgpNaW5pbWl6aW5nIHRoaXMgbG9zcyB3b3VsZCBjYXVzZSBgc3R5bGUoZ2VuZXJhdGVkX2ltYWdlKWAgdG8gYmUgY2xvc2UgdG8gYHN0eWxlKHJlZmVyZW5jZV9pbWFnZSlgLCB3aGlsZSBgY29udGVudChnZW5lcmF0ZWRfaW1hZ2UpYCB3b3VsZCBiZSBjbG9zZSB0byBgY29udGVudChnZW5lcmF0ZWRfaW1hZ2UpYCwgdGh1cyBhY2hpZXZpbmcgc3R5bGUgdHJhbnNmZXIgYXMgd2UgZGVmaW5lZCBpdC4KCkEgZnVuZGFtZW50YWwgb2JzZXJ2YXRpb24gbWFkZSBieSBHYXR5cyBldCBhbCBpcyB0aGF0IGRlZXAgY29udm9sdXRpb25hbCBuZXVyYWwgbmV0d29ya3Mgb2ZmZXIgcHJlY2lzZWx5IGEgd2F5IHRvIG1hdGhlbWF0aWNhbGx5IGRlZmluZWQgdGhlIGBzdHlsZWAgYW5kIGBjb250ZW50YCBmdW5jdGlvbnMuIExldCdzIHNlZSBob3cuCgojIyBUaGUgY29udGVudCBsb3NzCgpBcyB5b3UgYWxyZWFkeSBrbm93LCBhY3RpdmF0aW9ucyBmcm9tIGVhcmxpZXIgbGF5ZXJzIGluIGEgbmV0d29yayBjb250YWluIF9sb2NhbF8gaW5mb3JtYXRpb24gYWJvdXQgdGhlIGltYWdlLCB3aGlsZSBhY3RpdmF0aW9ucyBmcm9tIGhpZ2hlciBsYXllcnMgY29udGFpbiBpbmNyZWFzaW5nbHkgX2dsb2JhbF8gYW5kIF9hYnN0cmFjdF8gaW5mb3JtYXRpb24uIEZvcm11bGF0ZWQgaW4gYSBkaWZmZXJlbnQgd2F5LCB0aGUgYWN0aXZhdGlvbnMgb2YgdGhlIGRpZmZlcmVudCBsYXllcnMgb2YgYSBjb252bmV0IHByb3ZpZGUgYSBkZWNvbXBvc2l0aW9uIG9mIHRoZSBjb250ZW50cyBvZiBhbiBpbWFnZSBvdmVyIGRpZmZlcmVudCBzcGF0aWFsIHNjYWxlcy4gVGhlcmVmb3JlIHdlIGV4cGVjdCB0aGUgImNvbnRlbnQiIG9mIGFuIGltYWdlLCB3aGljaCBpcyBtb3JlIGdsb2JhbCBhbmQgbW9yZSBhYnN0cmFjdCwgdG8gYmUgY2FwdHVyZWQgYnkgdGhlIHJlcHJlc2VudGF0aW9ucyBvZiBhIHRvcCBsYXllciBvZiBhIGNvbnZuZXQuCgpBIGdvb2QgY2FuZGlkYXRlIGZvciBhIGNvbnRlbnQgbG9zcyB3b3VsZCB0aHVzIGJlIHRvIGNvbnNpZGVyIGEgcHJlLXRyYWluZWQgY29udm5ldCwgYW5kIGRlZmluZSBhcyBvdXIgbG9zcyB0aGUgTDIgbm9ybSBiZXR3ZWVuIHRoZSBhY3RpdmF0aW9ucyBvZiBhIHRvcCBsYXllciBjb21wdXRlZCBvdmVyIHRoZSB0YXJnZXQgaW1hZ2UgYW5kIHRoZSBhY3RpdmF0aW9ucyBvZiB0aGUgc2FtZSBsYXllciBjb21wdXRlZCBvdmVyIHRoZSBnZW5lcmF0ZWQgaW1hZ2UuIFRoaXMgd291bGQgZ3VhcmFudGVlIHRoYXQsIGFzIHNlZW4gZnJvbSB0aGUgdG9wIGxheWVyIG9mIHRoZSBjb252bmV0LCB0aGUgZ2VuZXJhdGVkIGltYWdlIHdpbGwgImxvb2sgc2ltaWxhciIgdG8gdGhlIG9yaWdpbmFsIHRhcmdldCBpbWFnZS4gQXNzdW1pbmcgdGhhdCB3aGF0IHRoZSB0b3AgbGF5ZXJzIG9mIGEgY29udm5ldCBzZWUgaXMgcmVhbGx5IHRoZSAiY29udGVudCIgb2YgdGhlaXIgaW5wdXQgaW1hZ2VzLCB0aGVuIHRoaXMgZG9lcyB3b3JrIGFzIGEgd2F5IHRvIHByZXNlcnZlIAppbWFnZSBjb250ZW50LgoKIyMgVGhlIHN0eWxlIGxvc3MKCgpXaGlsZSB0aGUgY29udGVudCBsb3NzIG9ubHkgbGV2ZXJhZ2VzIGEgc2luZ2xlIGhpZ2hlci11cCBsYXllciwgdGhlIHN0eWxlIGxvc3MgYXMgZGVmaW5lZCBpbiB0aGUgR2F0eXMgZXQgYWwuIHBhcGVyIGxldmVyYWdlcyBtdWx0aXBsZSBsYXllcnMgb2YgYSBjb252bmV0OiB3ZSBhaW0gYXQgY2FwdHVyaW5nIHRoZSBhcHBlYXJhbmNlIG9mIHRoZSBzdHlsZSByZWZlcmVuY2UgaW1hZ2UgYXQgYWxsIHNwYXRpYWwgc2NhbGVzIGV4dHJhY3RlZCBieSB0aGUgY29udm5ldCwgbm90IGp1c3QgYW55IHNpbmdsZSBzY2FsZS4KCkZvciB0aGUgc3R5bGUgbG9zcywgdGhlIEdhdHlzIGV0IGFsLiBwYXBlciBsZXZlcmFnZXMgdGhlICJHcmFtIG1hdHJpeCIgb2YgYSBsYXllcidzIGFjdGl2YXRpb25zLCBpLmUuIHRoZSBpbm5lciBwcm9kdWN0IGJldHdlZW4gdGhlIGZlYXR1cmUgbWFwcyBvZiBhIGdpdmVuIGxheWVyLiBUaGlzIGlubmVyIHByb2R1Y3QgY2FuIGJlIHVuZGVyc3Rvb2QgYXMgcmVwcmVzZW50aW5nIGEgbWFwIG9mIHRoZSBjb3JyZWxhdGlvbnMgYmV0d2VlbiB0aGUgZmVhdHVyZXMgb2YgYSBsYXllci4gVGhlc2UgZmVhdHVyZSBjb3JyZWxhdGlvbnMgY2FwdHVyZSB0aGUgc3RhdGlzdGljcyBvZiB0aGUgcGF0dGVybnMgb2YgYSBwYXJ0aWN1bGFyIHNwYXRpYWwgc2NhbGUsIHdoaWNoIGVtcGlyaWNhbGx5IGNvcnJlc3BvbmRzIHRvIHRoZSBhcHBlYXJhbmNlIG9mIHRoZSB0ZXh0dXJlcyBmb3VuZCBhdCB0aGlzIHNjYWxlLgoKSGVuY2UgdGhlIHN0eWxlIGxvc3MgYWltcyBhdCBwcmVzZXJ2aW5nIHNpbWlsYXIgaW50ZXJuYWwgY29ycmVsYXRpb25zIHdpdGhpbiB0aGUgYWN0aXZhdGlvbnMgb2YgZGlmZmVyZW50IGxheWVycywgYWNyb3NzIHRoZSBzdHlsZSByZWZlcmVuY2UgaW1hZ2UgYW5kIHRoZSBnZW5lcmF0ZWQgaW1hZ2UuIEluIHR1cm4sIHRoaXMgZ3VhcmFudGVlcyB0aGF0IHRoZSB0ZXh0dXJlcyBmb3VuZCBhdCBkaWZmZXJlbnQgc3BhdGlhbCBzY2FsZXMgd2lsbCBsb29rIHNpbWlsYXIgYWNyb3NzIHRoZSBzdHlsZSByZWZlcmVuY2UgaW1hZ2UgYW5kIHRoZSBnZW5lcmF0ZWQgaW1hZ2UuCgojIyBJbiBzaG9ydAoKCkluIHNob3J0LCB3ZSBjYW4gdXNlIGEgcHJlLXRyYWluZWQgY29udm5ldCB0byBkZWZpbmUgYSBsb3NzIHRoYXQgd2lsbDoKCiogUHJlc2VydmUgY29udGVudCBieSBtYWludGFpbmluZyBzaW1pbGFyIGhpZ2gtbGV2ZWwgbGF5ZXIgYWN0aXZhdGlvbnMgYmV0d2VlbiB0aGUgdGFyZ2V0IGNvbnRlbnQgaW1hZ2UgYW5kIHRoZSBnZW5lcmF0ZWQgaW1hZ2UuIFRoZSBjb252bmV0IHNob3VsZCAic2VlIiBib3RoIHRoZSB0YXJnZXQgaW1hZ2UgYW5kIHRoZSBnZW5lcmF0ZWQgaW1hZ2UgYXMgImNvbnRhaW5pbmcgdGhlIHNhbWUgdGhpbmdzIi4KKiBQcmVzZXJ2ZSBzdHlsZSBieSBtYWludGFpbmluZyBzaW1pbGFyIF9jb3JyZWxhdGlvbnNfIHdpdGhpbiBhY3RpdmF0aW9ucyBmb3IgYm90aCBsb3ctbGV2ZWwgbGF5ZXJzIGFuZCBoaWdoLWxldmVsIGxheWVycy4gSW5kZWVkLCBmZWF0dXJlIGNvcnJlbGF0aW9ucyBjYXB0dXJlIF90ZXh0dXJlc186IHRoZSBnZW5lcmF0ZWQgYW5kIHRoZSBzdHlsZSByZWZlcmVuY2UgaW1hZ2Ugc2hvdWxkIHNoYXJlIHRoZSBzYW1lIHRleHR1cmVzIGF0IGRpZmZlcmVudCBzcGF0aWFsIHNjYWxlcy4KCk5vdyBsZXQncyB0YWtlIGEgbG9vayBhdCBhIEtlcmFzIGltcGxlbWVudGF0aW9uIG9mIHRoZSBvcmlnaW5hbCAyMDE1IG5ldXJhbCBzdHlsZSB0cmFuc2ZlciBhbGdvcml0aG0uIEFzIHlvdSB3aWxsIHNlZSwgaXQgc2hhcmVzIGEgbG90IG9mIHNpbWlsYXJpdGllcyB3aXRoIHRoZSBEZWVwIERyZWFtIGltcGxlbWVudGF0aW9uIHdlIGRldmVsb3BlZCBpbiB0aGUgcHJldmlvdXMgc2VjdGlvbi4KCiMjIE5ldXJhbCBzdHlsZSB0cmFuc2ZlciBpbiBLZXJhcwoKCk5ldXJhbCBzdHlsZSB0cmFuc2ZlciBjYW4gYmUgaW1wbGVtZW50ZWQgdXNpbmcgYW55IHByZS10cmFpbmVkIGNvbnZuZXQuIEhlcmUgd2Ugd2lsbCB1c2UgdGhlIFZHRzE5IG5ldHdvcmssIHVzZWQgYnkgR2F0eXMgZXQgYWwgaW4gdGhlaXIgcGFwZXIuIFZHRzE5IGlzIGEgc2ltcGxlIHZhcmlhbnQgb2YgdGhlIFZHRzE2IG5ldHdvcmsgd2UgaW50cm9kdWNlZCBpbiBDaGFwdGVyIDUsIHdpdGggdGhyZWUgbW9yZSBjb252b2x1dGlvbmFsIGxheWVycy4KClRoaXMgaXMgb3VyIGdlbmVyYWwgcHJvY2VzczoKCiogU2V0IHVwIGEgbmV0d29yayB0aGF0IHdpbGwgY29tcHV0ZSBWR0cxOSBsYXllciBhY3RpdmF0aW9ucyBmb3IgdGhlIHN0eWxlIHJlZmVyZW5jZSBpbWFnZSwgdGhlIHRhcmdldCBpbWFnZSwgYW5kIHRoZSBnZW5lcmF0ZWQgaW1hZ2UgYXQgCnRoZSBzYW1lIHRpbWUuCiogVXNlIHRoZSBsYXllciBhY3RpdmF0aW9ucyBjb21wdXRlZCBvdmVyIHRoZXNlIHRocmVlIGltYWdlcyB0byBkZWZpbmUgdGhlIGxvc3MgZnVuY3Rpb24gZGVzY3JpYmVkIGFib3ZlLCB3aGljaCB3ZSB3aWxsIG1pbmltaXplIGluIG9yZGVyIAp0byBhY2hpZXZlIHN0eWxlIHRyYW5zZmVyLgoqIFNldCB1cCBhIGdyYWRpZW50IGRlc2NlbnQgcHJvY2VzcyB0byBtaW5pbWl6ZSB0aGlzIGxvc3MgZnVuY3Rpb24uCgoKTGV0J3Mgc3RhcnQgYnkgZGVmaW5pbmcgdGhlIHBhdGhzIHRvIHRoZSB0d28gaW1hZ2VzIHdlIGNvbnNpZGVyOiB0aGUgc3R5bGUgcmVmZXJlbmNlIGltYWdlIGFuZCB0aGUgdGFyZ2V0IGltYWdlLiBUbyBtYWtlIHN1cmUgdGhhdCBhbGwgaW1hZ2VzIHByb2Nlc3NlZCBzaGFyZSBzaW1pbGFyIHNpemVzICh3aWRlbHkgZGlmZmVyZW50IHNpemVzIHdvdWxkIG1ha2Ugc3R5bGUgdHJhbnNmZXIgbW9yZSBkaWZmaWN1bHQpLCB3ZSB3aWxsIGxhdGVyIHJlc2l6ZSB0aGVtIGFsbCB0byBhIHNoYXJlZCBoZWlnaHQgb2YgNDAwcHguCgpgYGB7cn0KbGlicmFyeShrZXJhcykKCiMgVGhpcyBpcyB0aGUgcGF0aCB0byB0aGUgaW1hZ2UgeW91IHdhbnQgdG8gdHJhbnNmb3JtLgp0YXJnZXRfaW1hZ2VfcGF0aCA8LSAic3R5bGVfdHJhbnNmZXIvcG9ydHJhaXQucG5nIiAKCiMgVGhpcyBpcyB0aGUgcGF0aCB0byB0aGUgc3R5bGUgaW1hZ2UuCnN0eWxlX3JlZmVyZW5jZV9pbWFnZV9wYXRoIDwtICJzdHlsZV90cmFuc2Zlci90cmFuc2Zlcl9zdHlsZV9yZWZlcmVuY2UucG5nIgoKIyBEaW1lbnNpb25zIG9mIHRoZSBnZW5lcmF0ZWQgcGljdHVyZS4KaW1nIDwtIGltYWdlX2xvYWQodGFyZ2V0X2ltYWdlX3BhdGgpCndpZHRoIDwtIGltZyRzaXplW1sxXV0KaGVpZ2h0IDwtIGltZyRzaXplW1syXV0KaW1nX25yb3dzIDwtIDQwMAppbWdfbmNvbHMgPC0gYXMuaW50ZWdlcih3aWR0aCAqIGltZ19ucm93cyAvIGhlaWdodCkgIApgYGAKCldlIHdpbGwgbmVlZCBzb21lIGF1eGlsaWFyeSBmdW5jdGlvbnMgZm9yIGxvYWRpbmcsIHByZS1wcm9jZXNzaW5nIGFuZCBwb3N0LXByb2Nlc3NpbmcgdGhlIGltYWdlcyB0aGF0IHdpbGwgZ28gaW4gYW5kIG91dCBvZiB0aGUgVkdHMTkgY29udm5ldDoKCmBgYHtyfQpwcmVwcm9jZXNzX2ltYWdlIDwtIGZ1bmN0aW9uKHBhdGgpIHsKICBpbWcgPC0gaW1hZ2VfbG9hZChwYXRoLCB0YXJnZXRfc2l6ZSA9IGMoaW1nX25yb3dzLCBpbWdfbmNvbHMpKSAlPiUKICAgIGltYWdlX3RvX2FycmF5KCkgJT4lCiAgICBhcnJheV9yZXNoYXBlKGMoMSwgZGltKC4pKSkKICBpbWFnZW5ldF9wcmVwcm9jZXNzX2lucHV0KGltZykKfQoKZGVwcm9jZXNzX2ltYWdlIDwtIGZ1bmN0aW9uKHgpIHsKICB4IDwtIHhbMSwsLF0KICAjIFJlbW92ZSB6ZXJvLWNlbnRlciBieSBtZWFuIHBpeGVsCiAgeFssLDFdIDwtIHhbLCwxXSArIDEwMy45MzkKICB4WywsMl0gPC0geFssLDJdICsgMTE2Ljc3OQogIHhbLCwzXSA8LSB4WywsM10gKyAxMjMuNjgKICAjICdCR1InLT4nUkdCJwogIHggPC0geFssLGMoMywyLDEpXQogIHhbeCA+IDI1NV0gPC0gMjU1CiAgeFt4IDwgMF0gPC0gMAogIHhbXSA8LSBhcy5pbnRlZ2VyKHgpLzI1NQogIHgKfQpgYGAKCkxldCdzIHNldCB1cCB0aGUgVkdHMTkgbmV0d29yay4gSXQgdGFrZXMgYXMgaW5wdXQgYSBiYXRjaCBvZiB0aHJlZSBpbWFnZXM6IHRoZSBzdHlsZS1yZWZlcmVuY2UgaW1hZ2UsIHRoZSB0YXJnZXQgaW1hZ2UsIGFuZCBhIHBsYWNlaG9sZGVyIHRoYXQgd2lsbCBjb250YWluIHRoZSBnZW5lcmF0ZWQgaW1hZ2UuIEEgcGxhY2Vob2xkZXIgaXMgYSBzeW1ib2xpYyB0ZW5zb3IsIHRoZSB2YWx1ZXMgb2Ygd2hpY2ggYXJlIHByb3ZpZGVkIGV4dGVybmFsbHkgdmlhIFIgYXJyYXlzLiBUaGUgc3R5bGUtcmVmZXJlbmNlIGFuZCB0YXJnZXQgaW1hZ2UgYXJlIHN0YXRpYyBhbmQgdGh1cyBkZWZpbmVkIHVzaW5nIGBrX2NvbnN0YW50YCwgd2hlcmVhcyB0aGUgdmFsdWVzIGNvbnRhaW5lZCBpbiB0aGUgcGxhY2Vob2xkZXIgb2YgdGhlIGdlbmVyYXRlZCBpbWFnZSB3aWxsIGNoYW5nZSBvdmVyIHRpbWUuCgpgYGB7cn0KdGFyZ2V0X2ltYWdlIDwtIGtfY29uc3RhbnQocHJlcHJvY2Vzc19pbWFnZSh0YXJnZXRfaW1hZ2VfcGF0aCkpCnN0eWxlX3JlZmVyZW5jZV9pbWFnZSA8LSBrX2NvbnN0YW50KAogIHByZXByb2Nlc3NfaW1hZ2Uoc3R5bGVfcmVmZXJlbmNlX2ltYWdlX3BhdGgpCikKCiMgVGhpcyBwbGFjZWhvbGRlciB3aWxsIGNvbnRhaW4gb3VyIGdlbmVyYXRlZCBpbWFnZQpjb21iaW5hdGlvbl9pbWFnZSA8LSBrX3BsYWNlaG9sZGVyKGMoMSwgaW1nX25yb3dzLCBpbWdfbmNvbHMsIDMpKSAKCiMgV2UgY29tYmluZSB0aGUgMyBpbWFnZXMgaW50byBhIHNpbmdsZSBiYXRjaAppbnB1dF90ZW5zb3IgPC0ga19jb25jYXRlbmF0ZShsaXN0KHRhcmdldF9pbWFnZSwgc3R5bGVfcmVmZXJlbmNlX2ltYWdlLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb21iaW5hdGlvbl9pbWFnZSksIGF4aXMgPSAxKQoKIyBXZSBidWlsZCB0aGUgVkdHMTkgbmV0d29yayB3aXRoIG91ciBiYXRjaCBvZiAzIGltYWdlcyBhcyBpbnB1dC4KIyBUaGUgbW9kZWwgd2lsbCBiZSBsb2FkZWQgd2l0aCBwcmUtdHJhaW5lZCBJbWFnZU5ldCB3ZWlnaHRzLgptb2RlbCA8LSBhcHBsaWNhdGlvbl92Z2cxOShpbnB1dF90ZW5zb3IgPSBpbnB1dF90ZW5zb3IsIAogICAgICAgICAgICAgICAgICAgICAgICAgICB3ZWlnaHRzID0gImltYWdlbmV0IiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGluY2x1ZGVfdG9wID0gRkFMU0UpCgpjYXQoIk1vZGVsIGxvYWRlZFxuIikKYGBgCgpMZXQncyBkZWZpbmUgdGhlIGNvbnRlbnQgbG9zcywgbWVhbnQgdG8gbWFrZSBzdXJlIHRoYXQgdGhlIHRvcCBsYXllciBvZiB0aGUgVkdHMTkgY29udm5ldCB3aWxsIGhhdmUgYSBzaW1pbGFyIHZpZXcgb2YgdGhlIHRhcmdldCBpbWFnZSBhbmQgdGhlIGdlbmVyYXRlZCBpbWFnZToKCmBgYHtyfQpjb250ZW50X2xvc3MgPC0gZnVuY3Rpb24oYmFzZSwgY29tYmluYXRpb24pIHsKICBrX3N1bShrX3NxdWFyZShjb21iaW5hdGlvbiAtIGJhc2UpKQp9CmBgYAoKTm93LCBoZXJlJ3MgdGhlIHN0eWxlIGxvc3MuIEl0IGxldmVyYWdlcyBhbiBhdXhpbGlhcnkgZnVuY3Rpb24gdG8gY29tcHV0ZSB0aGUgR3JhbSBtYXRyaXggb2YgYW4gaW5wdXQgbWF0cml4LCBpLmUuIGEgbWFwIG9mIHRoZSBjb3JyZWxhdGlvbnMgZm91bmQgaW4gdGhlIG9yaWdpbmFsIGZlYXR1cmUgbWF0cml4LgoKYGBge3J9CmdyYW1fbWF0cml4IDwtIGZ1bmN0aW9uKHgpIHsKICBmZWF0dXJlcyA8LSBrX2JhdGNoX2ZsYXR0ZW4oa19wZXJtdXRlX2RpbWVuc2lvbnMoeCwgYygzLCAxLCAyKSkpCiAgZ3JhbSA8LSBrX2RvdChmZWF0dXJlcywga190cmFuc3Bvc2UoZmVhdHVyZXMpKQogIGdyYW0KfQoKc3R5bGVfbG9zcyA8LSBmdW5jdGlvbihzdHlsZSwgY29tYmluYXRpb24pewogIFMgPC0gZ3JhbV9tYXRyaXgoc3R5bGUpCiAgQyA8LSBncmFtX21hdHJpeChjb21iaW5hdGlvbikKICBjaGFubmVscyA8LSAzCiAgc2l6ZSA8LSBpbWdfbnJvd3MqaW1nX25jb2xzCiAga19zdW0oa19zcXVhcmUoUyAtIEMpKSAvICg0ICogY2hhbm5lbHNeMiAgKiBzaXplXjIpCn0KYGBgCgpUbyB0aGVzZSB0d28gbG9zcyBjb21wb25lbnRzLCB3ZSBhZGQgYSB0aGlyZCBvbmUsIHRoZSAidG90YWwgdmFyaWF0aW9uIGxvc3MiLiBJdCBpcyBtZWFudCB0byBlbmNvdXJhZ2Ugc3BhdGlhbCBjb250aW51aXR5IGluIHRoZSBnZW5lcmF0ZWQgaW1hZ2UsIHRodXMgYXZvaWRpbmcgb3Zlcmx5IHBpeGVsYXRlZCByZXN1bHRzLiBZb3UgY291bGQgaW50ZXJwcmV0IGl0IGFzIGEgcmVndWxhcml6YXRpb24gbG9zcy4KCmBgYHtyfQp0b3RhbF92YXJpYXRpb25fbG9zcyA8LSBmdW5jdGlvbih4KSB7CiAgeV9paiAgPC0geFssMTooaW1nX25yb3dzIC0gMUwpLCAxOihpbWdfbmNvbHMgLSAxTCksXQogIHlfaTFqIDwtIHhbLDI6KGltZ19ucm93cyksIDE6KGltZ19uY29scyAtIDFMKSxdCiAgeV9pajEgPC0geFssMTooaW1nX25yb3dzIC0gMUwpLCAyOihpbWdfbmNvbHMpLF0KICBhIDwtIGtfc3F1YXJlKHlfaWogLSB5X2kxaikKICBiIDwtIGtfc3F1YXJlKHlfaWogLSB5X2lqMSkKICBrX3N1bShrX3BvdyhhICsgYiwgMS4yNSkpCn0KYGBgCgpUaGUgbG9zcyB0aGF0IHdlIG1pbmltaXplIGlzIGEgd2VpZ2h0ZWQgYXZlcmFnZSBvZiB0aGVzZSB0aHJlZSBsb3NzZXMuIFRvIGNvbXB1dGUgdGhlIGNvbnRlbnQgbG9zcywgd2Ugb25seSBsZXZlcmFnZSBvbmUgdG9wIGxheWVyLCB0aGUgYGJsb2NrNV9jb252MmAgbGF5ZXIsIHdoaWxlIGZvciB0aGUgc3R5bGUgbG9zcyB3ZSB1c2UgYSBsaXN0IG9mIGxheWVycyB0aGFuIHNwYW5zIGJvdGggbG93LWxldmVsIGFuZCBoaWdoLWxldmVsIGxheWVycy4gV2UgYWRkIHRoZSB0b3RhbCB2YXJpYXRpb24gbG9zcyBhdCB0aGUgZW5kLgoKRGVwZW5kaW5nIG9uIHRoZSBzdHlsZSByZWZlcmVuY2UgaW1hZ2UgYW5kIGNvbnRlbnQgaW1hZ2UgeW91IGFyZSB1c2luZywgeW91IHdpbGwgbGlrZWx5IHdhbnQgdG8gdHVuZSB0aGUgYGNvbnRlbnRfd2VpZ2h0YCBjb2VmZmljaWVudCwgdGhlIGNvbnRyaWJ1dGlvbiBvZiB0aGUgY29udGVudCBsb3NzIHRvIHRoZSB0b3RhbCBsb3NzLiBBIGhpZ2hlciBgY29udGVudF93ZWlnaHRgIG1lYW5zIHRoYXQgdGhlIHRhcmdldCBjb250ZW50IHdpbGwgYmUgbW9yZSByZWNvZ25pemFibGUgaW4gdGhlIGdlbmVyYXRlZCBpbWFnZS4KCmBgYHtyfQojIE5hbWVkIGxpc3QgbWFwcGluZyBsYXllciBuYW1lcyB0byBhY3RpdmF0aW9uIHRlbnNvcnMKb3V0cHV0c19kaWN0IDwtIGxhcHBseShtb2RlbCRsYXllcnMsIGBbW2AsICJvdXRwdXQiKQpuYW1lcyhvdXRwdXRzX2RpY3QpIDwtIGxhcHBseShtb2RlbCRsYXllcnMsIGBbW2AsICJuYW1lIikKCiMgTmFtZSBvZiBsYXllciB1c2VkIGZvciBjb250ZW50IGxvc3MKY29udGVudF9sYXllciA8LSAiYmxvY2s1X2NvbnYyIiAKCiMgTmFtZSBvZiBsYXllcnMgdXNlZCBmb3Igc3R5bGUgbG9zcwpzdHlsZV9sYXllcnMgPSBjKCJibG9jazFfY29udjEiLCAiYmxvY2syX2NvbnYxIiwKICAgICAgICAgICAgICAgICAiYmxvY2szX2NvbnYxIiwgImJsb2NrNF9jb252MSIsCiAgICAgICAgICAgICAgICAgImJsb2NrNV9jb252MSIpCgojIFdlaWdodHMgaW4gdGhlIHdlaWdodGVkIGF2ZXJhZ2Ugb2YgdGhlIGxvc3MgY29tcG9uZW50cwp0b3RhbF92YXJpYXRpb25fd2VpZ2h0IDwtIDFlLTQKc3R5bGVfd2VpZ2h0IDwtIDEuMApjb250ZW50X3dlaWdodCA8LSAwLjAyNQoKIyBEZWZpbmUgdGhlIGxvc3MgYnkgYWRkaW5nIGFsbCBjb21wb25lbnRzIHRvIGEgYGxvc3NgIHZhcmlhYmxlCmxvc3MgPC0ga192YXJpYWJsZSgwLjApIApsYXllcl9mZWF0dXJlcyA8LSBvdXRwdXRzX2RpY3RbW2NvbnRlbnRfbGF5ZXJdXSAKdGFyZ2V0X2ltYWdlX2ZlYXR1cmVzIDwtIGxheWVyX2ZlYXR1cmVzWzEsLCxdCmNvbWJpbmF0aW9uX2ZlYXR1cmVzIDwtIGxheWVyX2ZlYXR1cmVzWzMsLCxdCgpsb3NzIDwtIGxvc3MgKyBjb250ZW50X3dlaWdodCAqIGNvbnRlbnRfbG9zcyh0YXJnZXRfaW1hZ2VfZmVhdHVyZXMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbWJpbmF0aW9uX2ZlYXR1cmVzKQoKZm9yIChsYXllcl9uYW1lIGluIHN0eWxlX2xheWVycyl7CiAgbGF5ZXJfZmVhdHVyZXMgPC0gb3V0cHV0c19kaWN0W1tsYXllcl9uYW1lXV0KICBzdHlsZV9yZWZlcmVuY2VfZmVhdHVyZXMgPC0gbGF5ZXJfZmVhdHVyZXNbMiwsLF0KICBjb21iaW5hdGlvbl9mZWF0dXJlcyA8LSBsYXllcl9mZWF0dXJlc1szLCwsXQogIHNsIDwtIHN0eWxlX2xvc3Moc3R5bGVfcmVmZXJlbmNlX2ZlYXR1cmVzLCBjb21iaW5hdGlvbl9mZWF0dXJlcykKICBsb3NzIDwtIGxvc3MgKyAoKHN0eWxlX3dlaWdodCAvIGxlbmd0aChzdHlsZV9sYXllcnMpKSAqIHNsKQp9Cgpsb3NzIDwtIGxvc3MgKyAKICAodG90YWxfdmFyaWF0aW9uX3dlaWdodCAqIHRvdGFsX3ZhcmlhdGlvbl9sb3NzKGNvbWJpbmF0aW9uX2ltYWdlKSkKYGBgCgpGaW5hbGx5LCB3ZSBzZXQgdXAgdGhlIGdyYWRpZW50LWRlc2NlbnQgcHJvY2Vzcy4gSW4gdGhlIG9yaWdpbmFsIEdhdHlzIGV0IGFsLiBwYXBlciwgb3B0aW1pemF0aW9uIGlzIHBlcmZvcm1lZCB1c2luZyB0aGUgTC1CRkdTIGFsZ29yaXRobSwgc28gdGhhdCBpcyBhbHNvIHdoYXQgeW91J2xsIHVzZSBoZXJlLiBUaGlzIGlzIGEga2V5IGRpZmZlcmVuY2UgZnJvbSB0aGUgRGVlcERyZWFtIGV4YW1wbGUgaW4gc2VjdGlvbiA4LjIuIFRoZSBMLUJGR1MgYWxnb3JpdGhtIGlzIGF2YWlsYWJsZSB2aWEgdGhlIGBvcHRpbSgpYCBmdW5jdGlvbiwgYnV0IHRoZXJlIGFyZSB0d28gc2xpZ2h0IGxpbWl0YXRpb25zIHdpdGggdGhlIGBvcHRpbSgpYCBpbXBsZW1lbnRhdGlvbjoKCiogSXQgcmVxdWlyZXMgdGhhdCB5b3UgcGFzcyB0aGUgdmFsdWUgb2YgdGhlIGxvc3MgZnVuY3Rpb24gYW5kIHRoZSB2YWx1ZSBvZiB0aGUgZ3JhZGllbnRzIGFzIHR3byBzZXBhcmF0ZSBmdW5jdGlvbnMuCiogSXQgY2FuIG9ubHkgYmUgYXBwbGllZCB0byBmbGF0IHZlY3RvcnMsIHdoZXJlYXMgeW91IGhhdmUgYSAzRCBpbWFnZSBhcnJheS4KCkl0IHdvdWxkIGJlIGluZWZmaWNpZW50IHRvIGNvbXB1dGUgdGhlIHZhbHVlIG9mIHRoZSBsb3NzIGZ1bmN0aW9uIGFuZCB0aGUgdmFsdWUgb2YgdGhlIGdyYWRpZW50cyBpbmRlcGVuZGVudGx5LCBiZWNhdXNlIGRvaW5nIHNvIHdvdWxkIGxlYWQgdG8gYSBsb3Qgb2YgcmVkdW5kYW50IGNvbXB1dGF0aW9uIGJldHdlZW4gdGhlIHR3bzsgdGhlIHByb2Nlc3Mgd291bGQgYmUgYWxtb3N0IHR3aWNlIGFzIHNsb3cgYXMgY29tcHV0aW5nIHRoZW0gam9pbnRseS4gVG8gYnlwYXNzIHRoaXMsIHlvdSdsbCBzZXQgdXAgYW4gUjYgY2xhc3MgbmFtZWQgYEV2YWx1YXRvcmAgdGhhdCBjb21wdXRlcyBib3RoIHRoZSBsb3NzIHZhbHVlIGFuZCB0aGUgZ3JhZGllbnRzIHZhbHVlIGF0IG9uY2UsIHJldHVybnMgdGhlIGxvc3MgdmFsdWUgd2hlbiBjYWxsZWQgdGhlIGZpcnN0IHRpbWUsIGFuZCBjYWNoZXMgdGhlIGdyYWRpZW50cyBmb3IgdGhlIG5leHQgY2FsbC4KCmBgYHtyfQojIEdldCB0aGUgZ3JhZGllbnRzIG9mIHRoZSBnZW5lcmF0ZWQgaW1hZ2Ugd3J0IHRoZSBsb3NzCmdyYWRzIDwtIGtfZ3JhZGllbnRzKGxvc3MsIGNvbWJpbmF0aW9uX2ltYWdlKVtbMV1dIAoKIyBGdW5jdGlvbiB0byBmZXRjaCB0aGUgdmFsdWVzIG9mIHRoZSBjdXJyZW50IGxvc3MgYW5kIHRoZSBjdXJyZW50IGdyYWRpZW50cwpmZXRjaF9sb3NzX2FuZF9ncmFkcyA8LSBrX2Z1bmN0aW9uKGxpc3QoY29tYmluYXRpb25faW1hZ2UpLCBsaXN0KGxvc3MsIGdyYWRzKSkKCmV2YWxfbG9zc19hbmRfZ3JhZHMgPC0gZnVuY3Rpb24oaW1hZ2UpIHsKICBpbWFnZSA8LSBhcnJheV9yZXNoYXBlKGltYWdlLCBjKDEsIGltZ19ucm93cywgaW1nX25jb2xzLCAzKSkKICBvdXRzIDwtIGZldGNoX2xvc3NfYW5kX2dyYWRzKGxpc3QoaW1hZ2UpKQogIGxpc3QoCiAgICBsb3NzX3ZhbHVlID0gb3V0c1tbMV1dLAogICAgZ3JhZF92YWx1ZXMgPSBhcnJheV9yZXNoYXBlKG91dHNbWzJdXSwgZGltID0gbGVuZ3RoKG91dHNbWzJdXSkpCiAgKQp9CgpsaWJyYXJ5KFI2KQpFdmFsdWF0b3IgPC0gUjZDbGFzcygiRXZhbHVhdG9yIiwKICBwdWJsaWMgPSBsaXN0KAogICAgCiAgICBsb3NzX3ZhbHVlID0gTlVMTCwKICAgIGdyYWRfdmFsdWVzID0gTlVMTCwKICAgIAogICAgaW5pdGlhbGl6ZSA9IGZ1bmN0aW9uKCkgewogICAgICBzZWxmJGxvc3NfdmFsdWUgPC0gTlVMTAogICAgICBzZWxmJGdyYWRfdmFsdWVzIDwtIE5VTEwKICAgIH0sCiAgICAKICAgIGxvc3MgPSBmdW5jdGlvbih4KXsKICAgICAgbG9zc19hbmRfZ3JhZCA8LSBldmFsX2xvc3NfYW5kX2dyYWRzKHgpCiAgICAgIHNlbGYkbG9zc192YWx1ZSA8LSBsb3NzX2FuZF9ncmFkJGxvc3NfdmFsdWUKICAgICAgc2VsZiRncmFkX3ZhbHVlcyA8LSBsb3NzX2FuZF9ncmFkJGdyYWRfdmFsdWVzCiAgICAgIHNlbGYkbG9zc192YWx1ZQogICAgfSwKICAgIAogICAgZ3JhZHMgPSBmdW5jdGlvbih4KXsKICAgICAgZ3JhZF92YWx1ZXMgPC0gc2VsZiRncmFkX3ZhbHVlcwogICAgICBzZWxmJGxvc3NfdmFsdWUgPC0gTlVMTAogICAgICBzZWxmJGdyYWRfdmFsdWVzIDwtIE5VTEwKICAgICAgZ3JhZF92YWx1ZXMKICAgIH0KICApCikKCmV2YWx1YXRvciA8LSBFdmFsdWF0b3IkbmV3KCkKYGBgCgpGaW5hbGx5LCB5b3UgY2FuIHJ1biB0aGUgZ3JhZGllbnQtYXNjZW50IHByb2Nlc3MgdXNpbmcgdGhlIEwtQkZHUyBhbGdvcml0aG0sIHBsb3R0aW5nIHRoZSBjdXJyZW50IGdlbmVyYXRlZCBpbWFnZSBhdCBlYWNoIGl0ZXJhdGlvbiBvZiB0aGUgCmFsZ29yaXRobSAoaGVyZSwgYSBzaW5nbGUgaXRlcmF0aW9uIHJlcHJlc2VudHMgMjAgc3RlcHMgb2YgZ3JhZGllbnQgYXNjZW50KS4KCmBgYHtyfQppdGVyYXRpb25zIDwtIDIwCgpkbXMgPC0gYygxLCBpbWdfbnJvd3MsIGltZ19uY29scywgMykKCiMgVGhpcyBpcyB0aGUgaW5pdGlhbCBzdGF0ZTogdGhlIHRhcmdldCBpbWFnZS4KeCA8LSBwcmVwcm9jZXNzX2ltYWdlKHRhcmdldF9pbWFnZV9wYXRoKQojIE5vdGUgdGhhdCBvcHRpbSBjYW4gb25seSBwcm9jZXNzIGZsYXQgdmVjdG9ycy4KeCA8LSBhcnJheV9yZXNoYXBlKHgsIGRpbSA9IGxlbmd0aCh4KSkgIAoKZm9yIChpIGluIDE6aXRlcmF0aW9ucykgeyAKICAKICAjIFJ1bnMgTC1CRkdTIG92ZXIgdGhlIHBpeGVscyBvZiB0aGUgZ2VuZXJhdGVkIGltYWdlIHRvIG1pbmltaXplIHRoZSBuZXVyYWwgc3R5bGUgbG9zcy4KICBvcHQgPC0gb3B0aW0oCiAgICBhcnJheV9yZXNoYXBlKHgsIGRpbSA9IGxlbmd0aCh4KSksIAogICAgZm4gPSBldmFsdWF0b3IkbG9zcywgCiAgICBnciA9IGV2YWx1YXRvciRncmFkcywgCiAgICBtZXRob2QgPSAiTC1CRkdTLUIiLAogICAgY29udHJvbCA9IGxpc3QobWF4aXQgPSAxNSkKICApCiAgCiAgY2F0KCJMb3NzOiIsIG9wdCR2YWx1ZSwgIlxuIikKICAKICBpbWFnZSA8LSB4IDwtIG9wdCRwYXIKICBpbWFnZSA8LSBhcnJheV9yZXNoYXBlKGltYWdlLCBkbXMpCiAgCiAgaW0gPC0gZGVwcm9jZXNzX2ltYWdlKGltYWdlKQogIHBsb3QoYXMucmFzdGVyKGltKSkKfQpgYGAKCgohW10oc3R5bGVfdHJhbnNmZXIvcG9ydHJhaXRfc3R5bGVkLnBuZykKCktlZXAgaW4gbWluZCB0aGF0IHdoYXQgdGhpcyB0ZWNobmlxdWUgYWNoaWV2ZXMgaXMgbWVyZWx5IGEgZm9ybSBvZiBpbWFnZSByZS10ZXh0dXJpbmcsIG9yIHRleHR1cmUgdHJhbnNmZXIuIEl0IHdpbGwgd29yayBiZXN0IHdpdGggc3R5bGUgcmVmZXJlbmNlIGltYWdlcyB0aGF0IGFyZSBzdHJvbmdseSB0ZXh0dXJlZCBhbmQgaGlnaGx5IHNlbGYtc2ltaWxhciwgYW5kIHdpdGggY29udGVudCB0YXJnZXRzIHRoYXQgZG9uJ3QgcmVxdWlyZSBoaWdoIGxldmVscyBvZiBkZXRhaWxzIGluIG9yZGVyIHRvIGJlIHJlY29nbml6YWJsZS4gSXQgd291bGQgdHlwaWNhbGx5IG5vdCBiZSBhYmxlIHRvIGFjaGlldmUgZmFpcmx5IGFic3RyYWN0IGZlYXRzIHN1Y2ggYXMgInRyYW5zZmVycmluZyB0aGUgc3R5bGUgb2Ygb25lIHBvcnRyYWl0IHRvIGFub3RoZXIiLiBUaGUgYWxnb3JpdGhtIGlzIGNsb3NlciB0byBjbGFzc2ljYWwgc2lnbmFsIHByb2Nlc3NpbmcgdGhhbiB0byBBSSwgc28gZG9uJ3QgZXhwZWN0IGl0IHRvIHdvcmsgbGlrZSBtYWdpYyEKCkFkZGl0aW9uYWxseSwgZG8gbm90ZSB0aGF0IHJ1bm5pbmcgdGhpcyBzdHlsZSB0cmFuc2ZlciBhbGdvcml0aG0gaXMgcXVpdGUgc2xvdy4gSG93ZXZlciwgdGhlIHRyYW5zZm9ybWF0aW9uIG9wZXJhdGVkIGJ5IG91ciBzZXR1cCBpcyBzaW1wbGUgZW5vdWdoIHRoYXQgaXQgY2FuIGJlIGxlYXJuZWQgYnkgYSBzbWFsbCwgZmFzdCBmZWVkZm9yd2FyZCBjb252bmV0IGFzIHdlbGwgLS0gYXMgbG9uZyBhcyB5b3UgaGF2ZSBhcHByb3ByaWF0ZSB0cmFpbmluZyBkYXRhIGF2YWlsYWJsZS4gRmFzdCBzdHlsZSB0cmFuc2ZlciBjYW4gdGh1cyBiZSBhY2hpZXZlZCBieSBmaXJzdCBzcGVuZGluZyBhIGxvdCBvZiBjb21wdXRlIGN5Y2xlcyB0byBnZW5lcmF0ZSBpbnB1dC1vdXRwdXQgdHJhaW5pbmcgZXhhbXBsZXMgZm9yIGEgZml4ZWQgc3R5bGUgcmVmZXJlbmNlIGltYWdlLCB1c2luZyB0aGUgYWJvdmUgbWV0aG9kLCBhbmQgdGhlbiB0cmFpbmluZyBhIHNpbXBsZSBjb252bmV0IHRvIGxlYXJuIHRoaXMgc3R5bGUtc3BlY2lmaWMgdHJhbnNmb3JtYXRpb24uIE9uY2UgdGhhdCBpcyBkb25lLCBzdHlsaXppbmcgYSBnaXZlbiBpbWFnZSBpcyBpbnN0YW50YW5lb3VzOiBpdCdzIGEganVzdCBhIGZvcndhcmQgcGFzcyBvZiB0aGlzIHNtYWxsIGNvbnZuZXQuCgoKIyMgVGFrZSBhd2F5cwoKKiBTdHlsZSB0cmFuc2ZlciBjb25zaXN0cyBpbiBjcmVhdGluZyBhIG5ldyBpbWFnZSB0aGF0IHByZXNlcnZlcyB0aGUgImNvbnRlbnRzIiBvZiBhIHRhcmdldCBpbWFnZSB3aGlsZSBhbHNvIGNhcHR1cmluZyB0aGUgInN0eWxlIiBvZiBhIHJlZmVyZW5jZSBpbWFnZS4KKiAiQ29udGVudCIgY2FuIGJlIGNhcHR1cmVkIGJ5IHRoZSBoaWdoLWxldmVsIGFjdGl2YXRpb25zIG9mIGEgY29udm5ldC4KKiAiU3R5bGUiIGNhbiBiZSBjYXB0dXJlZCBieSB0aGUgaW50ZXJuYWwgY29ycmVsYXRpb25zIG9mIHRoZSBhY3RpdmF0aW9ucyBvZiBkaWZmZXJlbnQgbGF5ZXJzIG9mIGEgY29udm5ldC4KKiBIZW5jZSBkZWVwIGxlYXJuaW5nIGFsbG93cyBzdHlsZSB0cmFuc2ZlciB0byBiZSBmb3JtdWxhdGVkIGFzIGFuIG9wdGltaXphdGlvbiBwcm9jZXNzIHVzaW5nIGEgbG9zcyBkZWZpbmVkIHdpdGggYSBwcmUtdHJhaW5lZCBjb252bmV0LgoqIFN0YXJ0aW5nIGZyb20gdGhpcyBiYXNpYyBpZGVhLCBtYW55IHZhcmlhbnRzIGFuZCByZWZpbmVtZW50cyBhcmUgcG9zc2libGUhCg==