prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Google engine : latency caused by redirection
  The current implementation of the google engine has a little issue : there is a redirection for each request, but not for everyone.
  It's depend of the geoip : https://support.google.com/websearch/answer/873?hl=en
  
  If you look at the response time of the different searx instance, some time the google time is slow compare to the other engine, I guess this is this issue.
  
  One way to avoid this is to set the PREF cookie (set but http://www.google.com/ncr ). Of course there is an unique ID. On solution is to initialize the cookie at start of the searx instance : 
  
  ``` python
  pref_cookie = ''
  
  def get_google_pref_cookie():
      global pref_cookie
      if pref_cookie == '':
          resp = get('https://www.google.com/ncr', allow_redirects=False)
          pref_cookie = resp.cookies["PREF"]
      return pref_cookie
  ```
  
  and set the cookie in the request method : 
  
  ``` python
     params['cookies']['PREF'] = get_google_pref_cookie()
  ```
  
  The cookie is global to the searx instance, so in my opinion there is no privacy issue.
  
  Of course, if there searx instance is behind a router and share a public IP with other machine, the request are more "tagged", but isn't already the case since there is not all the normal header that a browser send ?
  
  Another solution is to revert to the previous solution that api.google.com, but the results are different from the "browser" version (see #92)
  
  
  </issue>
  <code>
  [start of searx/engines/google.py]
  1 #  Google (Web)
  2 #
  3 # @website     https://www.google.com
  4 # @provide-api yes (https://developers.google.com/custom-search/)
  5 #
  6 # @using-api   no
  7 # @results     HTML
  8 # @stable      no (HTML can change)
  9 # @parse       url, title, content, suggestion
  10 
  11 from urllib import urlencode
  12 from urlparse import urlparse, parse_qsl
  13 from lxml import html
  14 from searx.engines.xpath import extract_text, extract_url
  15 
  16 # engine dependent config
  17 categories = ['general']
  18 paging = True
  19 language_support = True
  20 
  21 # search-url
  22 google_hostname = 'www.google.com'
  23 search_path = '/search'
  24 redirect_path = '/url'
  25 images_path = '/images'
  26 search_url = ('https://' +
  27               google_hostname +
  28               search_path +
  29               '?{query}&start={offset}&gbv=1')
  30 
  31 # specific xpath variables
  32 results_xpath = '//li[@class="g"]'
  33 url_xpath = './/h3/a/@href'
  34 title_xpath = './/h3'
  35 content_xpath = './/span[@class="st"]'
  36 suggestion_xpath = '//p[@class="_Bmc"]'
  37 
  38 images_xpath = './/div/a'
  39 image_url_xpath = './@href'
  40 image_img_src_xpath = './img/@src'
  41 
  42 
  43 # remove google-specific tracking-url
  44 def parse_url(url_string):
  45     parsed_url = urlparse(url_string)
  46     if (parsed_url.netloc in [google_hostname, '']
  47             and parsed_url.path == redirect_path):
  48         query = dict(parse_qsl(parsed_url.query))
  49         return query['q']
  50     else:
  51         return url_string
  52 
  53 
  54 # do search-request
  55 def request(query, params):
  56     offset = (params['pageno'] - 1) * 10
  57 
  58     if params['language'] == 'all':
  59         language = 'en'
  60     else:
  61         language = params['language'].replace('_', '-').lower()
  62 
  63     params['url'] = search_url.format(offset=offset,
  64                                       query=urlencode({'q': query}))
  65 
  66     params['headers']['Accept-Language'] = language
  67 
  68     return params
  69 
  70 
  71 # get response from search-request
  72 def response(resp):
  73     results = []
  74 
  75     dom = html.fromstring(resp.text)
  76 
  77     # parse results
  78     for result in dom.xpath(results_xpath):
  79         title = extract_text(result.xpath(title_xpath)[0])
  80         try:
  81             url = parse_url(extract_url(result.xpath(url_xpath), search_url))
  82             parsed_url = urlparse(url)
  83             if (parsed_url.netloc == google_hostname
  84                     and parsed_url.path == search_path):
  85                 # remove the link to google news
  86                 continue
  87 
  88             # images result
  89             if (parsed_url.netloc == google_hostname
  90                     and parsed_url.path == images_path):
  91                 # only thumbnail image provided,
  92                 # so skipping image results
  93                 # results = results + parse_images(result)
  94                 pass
  95             else:
  96                 # normal result
  97                 content = extract_text(result.xpath(content_xpath)[0])
  98                 # append result
  99                 results.append({'url': url,
  100                                 'title': title,
  101                                 'content': content})
  102         except:
  103             continue
  104 
  105     # parse suggestion
  106     for suggestion in dom.xpath(suggestion_xpath):
  107         # append suggestion
  108         results.append({'suggestion': extract_text(suggestion)})
  109 
  110     # return results
  111     return results
  112 
  113 
  114 def parse_images(result):
  115     results = []
  116     for image in result.xpath(images_xpath):
  117         url = parse_url(extract_text(image.xpath(image_url_xpath)[0]))
  118         img_src = extract_text(image.xpath(image_img_src_xpath)[0])
  119 
  120         # append result
  121         results.append({'url': url,
  122                         'title': '',
  123                         'content': '',
  124                         'img_src': img_src,
  125                         'template': 'images.html'})
  126 
  127     return results
  128
  [end of searx/engines/google.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/searx/engines/google.py b/searx/engines/google.py
  --- a/searx/engines/google.py
  +++ b/searx/engines/google.py
  @@ -11,6 +11,7 @@
   from urllib import urlencode
   from urlparse import urlparse, parse_qsl
   from lxml import html
  +from searx.poolrequests import get
   from searx.engines.xpath import extract_text, extract_url
   
   # engine dependent config
  @@ -39,6 +40,17 @@
   image_url_xpath = './@href'
   image_img_src_xpath = './img/@src'
   
  +pref_cookie = ''
  +
  +
  +# see https://support.google.com/websearch/answer/873?hl=en
  +def get_google_pref_cookie():
  +    global pref_cookie
  +    if pref_cookie == '':
  +        resp = get('https://www.google.com/ncr', allow_redirects=False)
  +        pref_cookie = resp.cookies["PREF"]
  +    return pref_cookie
  +
   
   # remove google-specific tracking-url
   def parse_url(url_string):
  @@ -64,6 +76,7 @@
                                         query=urlencode({'q': query}))
   
       params['headers']['Accept-Language'] = language
  +    params['cookies']['PREF'] = get_google_pref_cookie()
   
       return params
  
verification_info: {"golden_diff": "diff --git a/searx/engines/google.py b/searx/engines/google.py\n--- a/searx/engines/google.py\n+++ b/searx/engines/google.py\n@@ -11,6 +11,7 @@\n from urllib import urlencode\n from urlparse import urlparse, parse_qsl\n from lxml import html\n+from searx.poolrequests import get\n from searx.engines.xpath import extract_text, extract_url\n \n # engine dependent config\n@@ -39,6 +40,17 @@\n image_url_xpath = './@href'\n image_img_src_xpath = './img/@src'\n \n+pref_cookie = ''\n+\n+\n+# see https://support.google.com/websearch/answer/873?hl=en\n+def get_google_pref_cookie():\n+    global pref_cookie\n+    if pref_cookie == '':\n+        resp = get('https://www.google.com/ncr', allow_redirects=False)\n+        pref_cookie = resp.cookies[\"PREF\"]\n+    return pref_cookie\n+\n \n # remove google-specific tracking-url\n def parse_url(url_string):\n@@ -64,6 +76,7 @@\n                                       query=urlencode({'q': query}))\n \n     params['headers']['Accept-Language'] = language\n+    params['cookies']['PREF'] = get_google_pref_cookie()\n \n     return params\n", "issue": "Google engine : latency caused by redirection\nThe current implementation of the google engine has a little issue : there is a redirection for each request, but not for everyone.\nIt's depend of the geoip : https://support.google.com/websearch/answer/873?hl=en\n\nIf you look at the response time of the different searx instance, some time the google time is slow compare to the other engine, I guess this is this issue.\n\nOne way to avoid this is to set the PREF cookie (set but http://www.google.com/ncr ). Of course there is an unique ID. On solution is to initialize the cookie at start of the searx instance : \n\n``` python\npref_cookie = ''\n\ndef get_google_pref_cookie():\n    global pref_cookie\n    if pref_cookie == '':\n        resp = get('https://www.google.com/ncr', allow_redirects=False)\n        pref_cookie = resp.cookies[\"PREF\"]\n    return pref_cookie\n```\n\nand set the cookie in the request method : \n\n``` python\n   params['cookies']['PREF'] = get_google_pref_cookie()\n```\n\nThe cookie is global to the searx instance, so in my opinion there is no privacy issue.\n\nOf course, if there searx instance is behind a router and share a public IP with other machine, the request are more \"tagged\", but isn't already the case since there is not all the normal header that a browser send ?\n\nAnother solution is to revert to the previous solution that api.google.com, but the results are different from the \"browser\" version (see #92)\n\n", "before_files": [{"content": "#  Google (Web)\n#\n# @website     https://www.google.com\n# @provide-api yes (https://developers.google.com/custom-search/)\n#\n# @using-api   no\n# @results     HTML\n# @stable      no (HTML can change)\n# @parse       url, title, content, suggestion\n\nfrom urllib import urlencode\nfrom urlparse import urlparse, parse_qsl\nfrom lxml import html\nfrom searx.engines.xpath import extract_text, extract_url\n\n# engine dependent config\ncategories = ['general']\npaging = True\nlanguage_support = True\n\n# search-url\ngoogle_hostname = 'www.google.com'\nsearch_path = '/search'\nredirect_path = '/url'\nimages_path = '/images'\nsearch_url = ('https://' +\n              google_hostname +\n              search_path +\n              '?{query}&start={offset}&gbv=1')\n\n# specific xpath variables\nresults_xpath = '//li[@class=\"g\"]'\nurl_xpath = './/h3/a/@href'\ntitle_xpath = './/h3'\ncontent_xpath = './/span[@class=\"st\"]'\nsuggestion_xpath = '//p[@class=\"_Bmc\"]'\n\nimages_xpath = './/div/a'\nimage_url_xpath = './@href'\nimage_img_src_xpath = './img/@src'\n\n\n# remove google-specific tracking-url\ndef parse_url(url_string):\n    parsed_url = urlparse(url_string)\n    if (parsed_url.netloc in [google_hostname, '']\n            and parsed_url.path == redirect_path):\n        query = dict(parse_qsl(parsed_url.query))\n        return query['q']\n    else:\n        return url_string\n\n\n# do search-request\ndef request(query, params):\n    offset = (params['pageno'] - 1) * 10\n\n    if params['language'] == 'all':\n        language = 'en'\n    else:\n        language = params['language'].replace('_', '-').lower()\n\n    params['url'] = search_url.format(offset=offset,\n                                      query=urlencode({'q': query}))\n\n    params['headers']['Accept-Language'] = language\n\n    return params\n\n\n# get response from search-request\ndef response(resp):\n    results = []\n\n    dom = html.fromstring(resp.text)\n\n    # parse results\n    for result in dom.xpath(results_xpath):\n        title = extract_text(result.xpath(title_xpath)[0])\n        try:\n            url = parse_url(extract_url(result.xpath(url_xpath), search_url))\n            parsed_url = urlparse(url)\n            if (parsed_url.netloc == google_hostname\n                    and parsed_url.path == search_path):\n                # remove the link to google news\n                continue\n\n            # images result\n            if (parsed_url.netloc == google_hostname\n                    and parsed_url.path == images_path):\n                # only thumbnail image provided,\n                # so skipping image results\n                # results = results + parse_images(result)\n                pass\n            else:\n                # normal result\n                content = extract_text(result.xpath(content_xpath)[0])\n                # append result\n                results.append({'url': url,\n                                'title': title,\n                                'content': content})\n        except:\n            continue\n\n    # parse suggestion\n    for suggestion in dom.xpath(suggestion_xpath):\n        # append suggestion\n        results.append({'suggestion': extract_text(suggestion)})\n\n    # return results\n    return results\n\n\ndef parse_images(result):\n    results = []\n    for image in result.xpath(images_xpath):\n        url = parse_url(extract_text(image.xpath(image_url_xpath)[0]))\n        img_src = extract_text(image.xpath(image_img_src_xpath)[0])\n\n        # append result\n        results.append({'url': url,\n                        'title': '',\n                        'content': '',\n                        'img_src': img_src,\n                        'template': 'images.html'})\n\n    return results\n", "path": "searx/engines/google.py"}]}